1935: [Shoi2007]Tree 园丁的烦恼

1935: [Shoi2007]Tree 园丁的烦恼

Time Limit: 15 Sec  Memory Limit: 357 MB

Submit: 648  Solved: 273

[Submit][Status][Discuss]

Sample Input

3 1 0 0 0 1 1 0 0 0 1 1

3

Source

```  1 /**************************************************************
2     Problem: 1935
3     User: HansBug
4     Language: Pascal
5     Result: Accepted
6     Time:7968 ms
7     Memory:100224 kb
8 ****************************************************************/
9
10 var
11    i,j,k,l,m,n,nx,ny:longint;
12    a:array[0..600000,1..2] of longint;
13    b:array[0..1200000,1..2] of longint;
14    c:array[0..4000000] of longint;
15    d:array[0..3000000,1..2] of longint;
16    e:array[0..3000000,1..4] of longint;
17 procedure swap(var x,y:longint);
18           var z:longint;
19           begin
20                z:=x;x:=y;y:=z;
21           end;
22 procedure sort(l,r:longint);
23           var i,j,x,y:longint;
24           begin
25                i:=l;j:=r;x:=d[(l+r) div 2,1];
26                repeat
27                      while d[i,1]<x do inc(i);
28                      while d[j,1]>x do dec(j);
29                      if i<=j then
30                         begin
31                              swap(d[i,1],d[j,1]);
32                              swap(d[i,2],d[j,2]);
33                              inc(i);dec(j);
34                         end;
35                until i>j;
36                if i<r then sort(i,r);
37                if l<j then sort(l,j);
38           end;
39 procedure sort0(l,r:longint);
40           var i,j,x,y,z:longint;
41           begin
42                i:=l;j:=r;x:=e[(l+r) div 2,1];y:=e[(l+r) div 2,2];z:=e[(l+r) div 2,3];
43                repeat
44                      while (e[i,1]<x) or ((e[i,1]=x) and (e[i,2]<y)) or ((e[i,1]=x) and (e[i,2]=y) and (e[i,3]>z)) do inc(i);
45                      while (e[j,1]>x) or ((e[j,1]=x) and (e[j,2]>y)) or ((e[j,1]=x) and (e[j,2]=y) and (e[j,3]<z)) do dec(j);
46                      if i<=j then
47                         begin
48                              swap(e[i,1],e[j,1]);
49                              swap(e[i,2],e[j,2]);
50                              swap(e[i,3],e[j,3]);
51                              inc(i);dec(j);
52                         end;
53                until i>j;
54                if i<r then sort0(i,r);
55                if l<j then sort0(l,j);
56           end;
57 procedure sort1(l,r:longint);
58           var i,j,x,y:longint;
59           begin
60                i:=l;j:=r;x:=e[(l+r) div 2,3];
61                repeat
62                      while e[i,3]<x do inc(i);
63                      while e[j,3]>x do dec(j);
64                      if i<=j then
65                         begin
66                              swap(e[i,1],e[j,1]);
67                              swap(e[i,2],e[j,2]);
68                              swap(e[i,3],e[j,3]);
69                              swap(e[i,4],e[j,4]);
70                              inc(i);dec(j);
71                         end;
72                until i>j;
73                if i<r then sort1(i,r);
74                if l<j then sort1(l,j);
75           end;
77          begin
78               if x<=0 then exit;
79               while x<=nx do
80                     begin
81                          inc(c[x],y);
82                          inc(x,x and (-x));
83                     end;
84          end;
85 function sum(x:longint):longint;
86          begin
87               sum:=0;
88               while x>0 do
89                     begin
90                          inc(sum,c[x]);
91                          dec(x,x and (-x));
92                     end;
93          end;
94 begin
96      for i:=1 to n do readln(a[i,1],a[i,2]);
97      for i:=1 to m do readln(b[i*2-1,1],b[i*2-1,2],b[i*2,1],b[i*2,2]);
98      for i:=1 to n do
99          begin
100               d[i,1]:=a[i,2];
101               d[i,2]:=i;
102          end;
103      for i:=1 to m*2 do
104          begin
105               d[n+i,1]:=b[i,2];
106               d[n+i,2]:=-i;
107          end;
108      sort(1,n+m*2);j:=0;d[0,1]:=-1;
109      for i:=1 to n+m*2 do
110          begin
111               if d[i,1]<>d[i-1,1] then inc(j);
112               if d[i,2]>0 then a[d[i,2],2]:=j else b[-d[i,2],2]:=j;
113          end;
114      nx:=j;
115      for i:=1 to m do
116          begin
117               e[i*4-3,1]:=b[i*2-1,1]-1;e[i*4-3,2]:=b[i*2-1,2]-1;
118               e[i*4-2,1]:=b[i*2-1,1]-1;e[i*4-2,2]:=b[i*2,2];
119               e[i*4-1,1]:=b[i*2,1];e[i*4-1,2]:=b[i*2-1,2]-1;
120               e[i*4,1]:=b[i*2,1];e[i*4,2]:=b[i*2,2];
121          end;
122      for i:=1 to n do begin e[m*4+i,1]:=a[i,1];e[m*4+i,2]:=a[i,2]; end;
123      for i:=1 to m*4+n do e[i,3]:=i;
124      sort0(1,m*4+n);
125      fillchar(c,sizeof(c),0);
126      for i:=1 to m*4+n do if e[i,3]<=(m*4) then e[i,4]:=sum(e[i,2]) else add(e[i,2],1);
127      sort1(1,m*4+n);
128      for i:=1 to m do writeln(e[i*4,4]-e[i*4-1,4]-e[i*4-2,4]+e[i*4-3,4]);
130 end.```

251 篇文章37 人订阅

0 条评论

相关文章

36460

Sweet Snippet 之 Bounce Setting

又是一篇Sweet Snippet，自己看来都觉得过小，不足以成篇，不过自觉有些趣味，也就随便记一记了，权当自娱自乐 ：）

7310

34280

1026 逃跑的拉尔夫

1026 逃跑的拉尔夫 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 年轻的...

33460

29960

9120

382100

67790

40150