#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <map>
using namespace std;
struct A
{
int l,r;
int nxl,nxr;
pair < int , int > ans;
map < int , int > all;
}Node[1000005];
int all[200005],now=1;
int ans[200005];
int l[200005],r[200005];
vector < pair < int , int > > query[200005];
int x[200005],y[200005];
vector < pair < int , int > > in[200005];
vector < pair < int , int > > out[200005];
vector < pair < int , int > > out2[200005];
pair < int , int > operator+(pair < int , int > a,pair < int , int > b)
{
return make_pair(max(a.first,b.first),min(a.second,b.second));
}
void build(int l,int r,int here)
{
Node[here].l=l;
Node[here].r=r;
Node[here].all[-1]++;
if(l==r)
{
Node[here].ans=make_pair(0,2e9);
return;
}
Node[here].nxl=now++;
Node[here].nxr=now++;
build(l,(l+r)/2,Node[here].nxl);
build((l+r)/2+1,r,Node[here].nxr);
Node[here].ans=Node[Node[here].nxl].ans+Node[Node[here].nxr].ans;
}
void cha(int where,pair < int , int > con,int here)
{
if(where==Node[here].l&&where==Node[here].r)
{
Node[here].ans=con;
return;
}
if(where<=(Node[here].l+Node[here].r)/2) cha(where,con,Node[here].nxl);
else cha(where,con,Node[here].nxr);
Node[here].ans=Node[Node[here].nxl].ans+Node[Node[here].nxr].ans;
}
void add(int where,int how,int here)
{
Node[here].all[how]++;
//printf("aa %d %d %d\n",where,how,here);
if(where==Node[here].l&&where==Node[here].r) return;
if(where<=(Node[here].l+Node[here].r)/2) add(where,how,Node[here].nxl);
else add(where,how,Node[here].nxr);
}
void del(int where,int how,int here)
{
//printf("%d\n",how);
Node[here].all[how]--;
if(Node[here].all[how]==0) Node[here].all.erase(how);
if(where==Node[here].l&&where==Node[here].r) return;
if(where<=(Node[here].l+Node[here].r)/2) del(where,how,Node[here].nxl);
else del(where,how,Node[here].nxr);
}
int Find2(int l,int r,int here)
{
if(l==Node[here].l&&r==Node[here].r)
{
//printf("%d %d %d %d\n",l,r,prev(Node[here].all.end())->first,prev(Node[here].all.end())->second);
return prev(Node[here].all.end())->first;
}
if(r<=(Node[here].l+Node[here].r)/2) return Find2(l,r,Node[here].nxl);
else if(l>(Node[here].l+Node[here].r)/2) return Find2(l,r,Node[here].nxr);
else return max(Find2(l,(Node[here].l+Node[here].r)/2,Node[here].nxl),Find2((Node[here].l+Node[here].r)/2+1,r,Node[here].nxr));
}
pair < int , int > Find(int l,int r,int here)
{
if(l==Node[here].l&&r==Node[here].r) return Node[here].ans;
if(r<=(Node[here].l+Node[here].r)/2) return Find(l,r,Node[here].nxl);
else if(l>(Node[here].l+Node[here].r)/2) return Find(l,r,Node[here].nxr);
else return Find(l,(Node[here].l+Node[here].r)/2,Node[here].nxl)+Find((Node[here].l+Node[here].r)/2+1,r,Node[here].nxr);
}
pair < int , int > tt;
int main()
{
int N,M,ok=0,i,j;
scanf("%d",&N);
for(i=1;i<=N;i++)
{
scanf("%d %d %d",&all[i],&l[i],&r[i]);
if(i-l[i]>=1)
{
in[max(1,i-r[i])].push_back(make_pair(i,all[i]));
out[i-l[i]+1].push_back(make_pair(i,all[i]));
}
}
scanf("%d",&M);
for(i=0;i<M;i++)
{
scanf("%d %d",&x[i],&y[i]);
query[x[i]].push_back(make_pair(y[i],i));
ans[i]=-1;
}
build(1,N,0);
if(N<=2000)
{
for(i=1;i<=N;i++)
{
for(j=i+1;j<=N;j++)
{
if(i+l[i]<=j&&i+r[i]>=j&&j-r[j]<=i&&j-l[j]>=i)
{
//printf("%d %d %d\n",i,j,abs(all[i]-all[j]));
out2[i+1].push_back(make_pair(j,abs(all[i]-all[j])));
add(j,abs(all[i]-all[j]),0);
}
}
}
for(i=1;i<=N;i++)
{
//for(auto j:in[i]) add(j.first,j.second,0);
for(auto j:out2[i]) del(j.first,j.second,0);
for(auto j:query[i]) ans[j.second]=Find2(i,j.first,0);
}
}
else
{
for(i=1;i<=N;i++)
{
for(auto j:in[i]) cha(j.first,make_pair(j.second,j.second),0);
for(auto j:out[i]) cha(j.first,make_pair(0,2e9),0);
for(j=0;j<M;j++)
{
if(i>=x[j]&&i+l[i]<=y[j])
{
tt=Find(i+l[i],min(y[j],i+r[i]),0);
if(tt.first) ans[j]=max(ans[j],abs(all[i]-tt.first));
if(tt.second!=2000000000) ans[j]=max(ans[j],abs(all[i]-tt.second));
}
}
}
}
for(j=0;j<M;j++) printf("%d\n",ans[j]);
return 0;
}
Compilation message
antennas.cpp: In function 'int main()':
antennas.cpp:97:13: warning: unused variable 'ok' [-Wunused-variable]
97 | int N,M,ok=0,i,j;
| ^~
antennas.cpp:98:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
98 | scanf("%d",&N);
| ~~~~~^~~~~~~~~
antennas.cpp:101:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
101 | scanf("%d %d %d",&all[i],&l[i],&r[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:108:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
108 | scanf("%d",&M);
| ~~~~~^~~~~~~~~
antennas.cpp:111:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
111 | scanf("%d %d",&x[i],&y[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
59 ms |
89836 KB |
Output is correct |
2 |
Correct |
75 ms |
91244 KB |
Output is correct |
3 |
Correct |
64 ms |
90368 KB |
Output is correct |
4 |
Correct |
72 ms |
91116 KB |
Output is correct |
5 |
Correct |
64 ms |
90476 KB |
Output is correct |
6 |
Correct |
73 ms |
90988 KB |
Output is correct |
7 |
Correct |
68 ms |
90604 KB |
Output is correct |
8 |
Correct |
72 ms |
91116 KB |
Output is correct |
9 |
Correct |
58 ms |
89836 KB |
Output is correct |
10 |
Correct |
74 ms |
91116 KB |
Output is correct |
11 |
Correct |
57 ms |
89580 KB |
Output is correct |
12 |
Correct |
69 ms |
90860 KB |
Output is correct |
13 |
Correct |
58 ms |
89708 KB |
Output is correct |
14 |
Correct |
60 ms |
89836 KB |
Output is correct |
15 |
Correct |
59 ms |
89708 KB |
Output is correct |
16 |
Correct |
58 ms |
89708 KB |
Output is correct |
17 |
Correct |
59 ms |
89708 KB |
Output is correct |
18 |
Correct |
58 ms |
89728 KB |
Output is correct |
19 |
Correct |
58 ms |
89708 KB |
Output is correct |
20 |
Correct |
58 ms |
89852 KB |
Output is correct |
21 |
Correct |
66 ms |
89708 KB |
Output is correct |
22 |
Correct |
59 ms |
89836 KB |
Output is correct |
23 |
Correct |
58 ms |
89708 KB |
Output is correct |
24 |
Correct |
64 ms |
89820 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
59 ms |
89836 KB |
Output is correct |
2 |
Correct |
75 ms |
91244 KB |
Output is correct |
3 |
Correct |
64 ms |
90368 KB |
Output is correct |
4 |
Correct |
72 ms |
91116 KB |
Output is correct |
5 |
Correct |
64 ms |
90476 KB |
Output is correct |
6 |
Correct |
73 ms |
90988 KB |
Output is correct |
7 |
Correct |
68 ms |
90604 KB |
Output is correct |
8 |
Correct |
72 ms |
91116 KB |
Output is correct |
9 |
Correct |
58 ms |
89836 KB |
Output is correct |
10 |
Correct |
74 ms |
91116 KB |
Output is correct |
11 |
Correct |
57 ms |
89580 KB |
Output is correct |
12 |
Correct |
69 ms |
90860 KB |
Output is correct |
13 |
Correct |
58 ms |
89708 KB |
Output is correct |
14 |
Correct |
60 ms |
89836 KB |
Output is correct |
15 |
Correct |
59 ms |
89708 KB |
Output is correct |
16 |
Correct |
58 ms |
89708 KB |
Output is correct |
17 |
Correct |
59 ms |
89708 KB |
Output is correct |
18 |
Correct |
58 ms |
89728 KB |
Output is correct |
19 |
Correct |
58 ms |
89708 KB |
Output is correct |
20 |
Correct |
58 ms |
89852 KB |
Output is correct |
21 |
Correct |
66 ms |
89708 KB |
Output is correct |
22 |
Correct |
59 ms |
89836 KB |
Output is correct |
23 |
Correct |
58 ms |
89708 KB |
Output is correct |
24 |
Correct |
64 ms |
89820 KB |
Output is correct |
25 |
Correct |
330 ms |
106732 KB |
Output is correct |
26 |
Correct |
1965 ms |
158244 KB |
Output is correct |
27 |
Correct |
1438 ms |
144748 KB |
Output is correct |
28 |
Correct |
2156 ms |
165996 KB |
Output is correct |
29 |
Correct |
468 ms |
111980 KB |
Output is correct |
30 |
Correct |
2236 ms |
166804 KB |
Output is correct |
31 |
Correct |
159 ms |
96768 KB |
Output is correct |
32 |
Correct |
2144 ms |
165996 KB |
Output is correct |
33 |
Correct |
663 ms |
121452 KB |
Output is correct |
34 |
Correct |
1954 ms |
161260 KB |
Output is correct |
35 |
Correct |
957 ms |
131036 KB |
Output is correct |
36 |
Correct |
2222 ms |
168096 KB |
Output is correct |
37 |
Correct |
139 ms |
94188 KB |
Output is correct |
38 |
Correct |
183 ms |
96408 KB |
Output is correct |
39 |
Correct |
87 ms |
92012 KB |
Output is correct |
40 |
Correct |
186 ms |
96420 KB |
Output is correct |
41 |
Correct |
160 ms |
95340 KB |
Output is correct |
42 |
Correct |
188 ms |
96364 KB |
Output is correct |
43 |
Correct |
110 ms |
93036 KB |
Output is correct |
44 |
Correct |
182 ms |
96492 KB |
Output is correct |
45 |
Correct |
95 ms |
92268 KB |
Output is correct |
46 |
Correct |
184 ms |
96492 KB |
Output is correct |
47 |
Correct |
102 ms |
92524 KB |
Output is correct |
48 |
Correct |
183 ms |
96364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
365 ms |
112356 KB |
Output is correct |
2 |
Correct |
416 ms |
114788 KB |
Output is correct |
3 |
Correct |
291 ms |
107240 KB |
Output is correct |
4 |
Correct |
419 ms |
114916 KB |
Output is correct |
5 |
Correct |
196 ms |
101224 KB |
Output is correct |
6 |
Correct |
421 ms |
114788 KB |
Output is correct |
7 |
Correct |
362 ms |
111588 KB |
Output is correct |
8 |
Correct |
428 ms |
114788 KB |
Output is correct |
9 |
Correct |
94 ms |
93676 KB |
Output is correct |
10 |
Correct |
410 ms |
114788 KB |
Output is correct |
11 |
Correct |
269 ms |
105452 KB |
Output is correct |
12 |
Correct |
408 ms |
114788 KB |
Output is correct |
13 |
Correct |
250 ms |
114568 KB |
Output is correct |
14 |
Correct |
246 ms |
114148 KB |
Output is correct |
15 |
Correct |
225 ms |
112824 KB |
Output is correct |
16 |
Correct |
234 ms |
112928 KB |
Output is correct |
17 |
Correct |
257 ms |
114660 KB |
Output is correct |
18 |
Correct |
235 ms |
113252 KB |
Output is correct |
19 |
Correct |
239 ms |
113640 KB |
Output is correct |
20 |
Correct |
243 ms |
113896 KB |
Output is correct |
21 |
Correct |
240 ms |
114532 KB |
Output is correct |
22 |
Correct |
240 ms |
113764 KB |
Output is correct |
23 |
Correct |
240 ms |
113892 KB |
Output is correct |
24 |
Correct |
227 ms |
112696 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
59 ms |
89836 KB |
Output is correct |
2 |
Correct |
75 ms |
91244 KB |
Output is correct |
3 |
Correct |
64 ms |
90368 KB |
Output is correct |
4 |
Correct |
72 ms |
91116 KB |
Output is correct |
5 |
Correct |
64 ms |
90476 KB |
Output is correct |
6 |
Correct |
73 ms |
90988 KB |
Output is correct |
7 |
Correct |
68 ms |
90604 KB |
Output is correct |
8 |
Correct |
72 ms |
91116 KB |
Output is correct |
9 |
Correct |
58 ms |
89836 KB |
Output is correct |
10 |
Correct |
74 ms |
91116 KB |
Output is correct |
11 |
Correct |
57 ms |
89580 KB |
Output is correct |
12 |
Correct |
69 ms |
90860 KB |
Output is correct |
13 |
Correct |
58 ms |
89708 KB |
Output is correct |
14 |
Correct |
60 ms |
89836 KB |
Output is correct |
15 |
Correct |
59 ms |
89708 KB |
Output is correct |
16 |
Correct |
58 ms |
89708 KB |
Output is correct |
17 |
Correct |
59 ms |
89708 KB |
Output is correct |
18 |
Correct |
58 ms |
89728 KB |
Output is correct |
19 |
Correct |
58 ms |
89708 KB |
Output is correct |
20 |
Correct |
58 ms |
89852 KB |
Output is correct |
21 |
Correct |
66 ms |
89708 KB |
Output is correct |
22 |
Correct |
59 ms |
89836 KB |
Output is correct |
23 |
Correct |
58 ms |
89708 KB |
Output is correct |
24 |
Correct |
64 ms |
89820 KB |
Output is correct |
25 |
Correct |
330 ms |
106732 KB |
Output is correct |
26 |
Correct |
1965 ms |
158244 KB |
Output is correct |
27 |
Correct |
1438 ms |
144748 KB |
Output is correct |
28 |
Correct |
2156 ms |
165996 KB |
Output is correct |
29 |
Correct |
468 ms |
111980 KB |
Output is correct |
30 |
Correct |
2236 ms |
166804 KB |
Output is correct |
31 |
Correct |
159 ms |
96768 KB |
Output is correct |
32 |
Correct |
2144 ms |
165996 KB |
Output is correct |
33 |
Correct |
663 ms |
121452 KB |
Output is correct |
34 |
Correct |
1954 ms |
161260 KB |
Output is correct |
35 |
Correct |
957 ms |
131036 KB |
Output is correct |
36 |
Correct |
2222 ms |
168096 KB |
Output is correct |
37 |
Correct |
139 ms |
94188 KB |
Output is correct |
38 |
Correct |
183 ms |
96408 KB |
Output is correct |
39 |
Correct |
87 ms |
92012 KB |
Output is correct |
40 |
Correct |
186 ms |
96420 KB |
Output is correct |
41 |
Correct |
160 ms |
95340 KB |
Output is correct |
42 |
Correct |
188 ms |
96364 KB |
Output is correct |
43 |
Correct |
110 ms |
93036 KB |
Output is correct |
44 |
Correct |
182 ms |
96492 KB |
Output is correct |
45 |
Correct |
95 ms |
92268 KB |
Output is correct |
46 |
Correct |
184 ms |
96492 KB |
Output is correct |
47 |
Correct |
102 ms |
92524 KB |
Output is correct |
48 |
Correct |
183 ms |
96364 KB |
Output is correct |
49 |
Correct |
365 ms |
112356 KB |
Output is correct |
50 |
Correct |
416 ms |
114788 KB |
Output is correct |
51 |
Correct |
291 ms |
107240 KB |
Output is correct |
52 |
Correct |
419 ms |
114916 KB |
Output is correct |
53 |
Correct |
196 ms |
101224 KB |
Output is correct |
54 |
Correct |
421 ms |
114788 KB |
Output is correct |
55 |
Correct |
362 ms |
111588 KB |
Output is correct |
56 |
Correct |
428 ms |
114788 KB |
Output is correct |
57 |
Correct |
94 ms |
93676 KB |
Output is correct |
58 |
Correct |
410 ms |
114788 KB |
Output is correct |
59 |
Correct |
269 ms |
105452 KB |
Output is correct |
60 |
Correct |
408 ms |
114788 KB |
Output is correct |
61 |
Correct |
250 ms |
114568 KB |
Output is correct |
62 |
Correct |
246 ms |
114148 KB |
Output is correct |
63 |
Correct |
225 ms |
112824 KB |
Output is correct |
64 |
Correct |
234 ms |
112928 KB |
Output is correct |
65 |
Correct |
257 ms |
114660 KB |
Output is correct |
66 |
Correct |
235 ms |
113252 KB |
Output is correct |
67 |
Correct |
239 ms |
113640 KB |
Output is correct |
68 |
Correct |
243 ms |
113896 KB |
Output is correct |
69 |
Correct |
240 ms |
114532 KB |
Output is correct |
70 |
Correct |
240 ms |
113764 KB |
Output is correct |
71 |
Correct |
240 ms |
113892 KB |
Output is correct |
72 |
Correct |
227 ms |
112696 KB |
Output is correct |
73 |
Execution timed out |
3081 ms |
123236 KB |
Time limit exceeded |
74 |
Halted |
0 ms |
0 KB |
- |