#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
using namespace std;
struct A
{
int l,r;
int nxl,nxr;
pair < int , int > ans;
}Node[1000005];
int all[1000005],now=1;
int ans[1000005];
int l[1000005],r[1000005];
vector < pair < int , int > > query[1000005];
int x[1000005],y[1000005];
vector < pair < int , int > > in[1000005];
vector < pair < int , int > > out[1000005];
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;
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;
}
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]);
for(j=x[i];j<=y[i];j++) query[j].push_back(make_pair(y[i],i));
}
build(1,N,0);
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(auto j:query[i])
{
if(i+l[i]<=j.first)
{
tt=Find(i+l[i],min(j.first,i+r[i]),0);
if(tt.first) ans[j.second]=max(ans[j.second],abs(all[i]-tt.first));
if(tt.second!=2000000000) ans[j.second]=max(ans[j.second],abs(all[i]-tt.second));
}
}
}
for(i=0;i<M;i++)
{
if(ans[i]==0) printf("-1\n");
else printf("%d\n",ans[i]);
}
return 0;
}
Compilation message
antennas.cpp: In function 'int main()':
antennas.cpp:61:13: warning: unused variable 'ok' [-Wunused-variable]
61 | int N,M,ok=0,i,j;
| ^~
antennas.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
62 | scanf("%d",&N);
| ~~~~~^~~~~~~~~
antennas.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
65 | scanf("%d %d %d",&all[i],&l[i],&r[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
72 | scanf("%d",&M);
| ~~~~~^~~~~~~~~
antennas.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
75 | scanf("%d %d",&x[i],&y[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
55 ms |
94316 KB |
Output is correct |
2 |
Correct |
57 ms |
94572 KB |
Output is correct |
3 |
Correct |
57 ms |
94700 KB |
Output is correct |
4 |
Correct |
56 ms |
94572 KB |
Output is correct |
5 |
Correct |
64 ms |
94444 KB |
Output is correct |
6 |
Correct |
55 ms |
94444 KB |
Output is correct |
7 |
Correct |
67 ms |
94720 KB |
Output is correct |
8 |
Correct |
66 ms |
94572 KB |
Output is correct |
9 |
Correct |
55 ms |
94444 KB |
Output is correct |
10 |
Correct |
63 ms |
94580 KB |
Output is correct |
11 |
Correct |
57 ms |
94444 KB |
Output is correct |
12 |
Correct |
63 ms |
94576 KB |
Output is correct |
13 |
Correct |
57 ms |
94444 KB |
Output is correct |
14 |
Correct |
58 ms |
94572 KB |
Output is correct |
15 |
Correct |
59 ms |
94572 KB |
Output is correct |
16 |
Correct |
56 ms |
94572 KB |
Output is correct |
17 |
Correct |
60 ms |
94572 KB |
Output is correct |
18 |
Correct |
55 ms |
94608 KB |
Output is correct |
19 |
Correct |
56 ms |
94316 KB |
Output is correct |
20 |
Correct |
54 ms |
94572 KB |
Output is correct |
21 |
Correct |
58 ms |
94588 KB |
Output is correct |
22 |
Correct |
71 ms |
94572 KB |
Output is correct |
23 |
Correct |
55 ms |
94572 KB |
Output is correct |
24 |
Correct |
56 ms |
94504 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
55 ms |
94316 KB |
Output is correct |
2 |
Correct |
57 ms |
94572 KB |
Output is correct |
3 |
Correct |
57 ms |
94700 KB |
Output is correct |
4 |
Correct |
56 ms |
94572 KB |
Output is correct |
5 |
Correct |
64 ms |
94444 KB |
Output is correct |
6 |
Correct |
55 ms |
94444 KB |
Output is correct |
7 |
Correct |
67 ms |
94720 KB |
Output is correct |
8 |
Correct |
66 ms |
94572 KB |
Output is correct |
9 |
Correct |
55 ms |
94444 KB |
Output is correct |
10 |
Correct |
63 ms |
94580 KB |
Output is correct |
11 |
Correct |
57 ms |
94444 KB |
Output is correct |
12 |
Correct |
63 ms |
94576 KB |
Output is correct |
13 |
Correct |
57 ms |
94444 KB |
Output is correct |
14 |
Correct |
58 ms |
94572 KB |
Output is correct |
15 |
Correct |
59 ms |
94572 KB |
Output is correct |
16 |
Correct |
56 ms |
94572 KB |
Output is correct |
17 |
Correct |
60 ms |
94572 KB |
Output is correct |
18 |
Correct |
55 ms |
94608 KB |
Output is correct |
19 |
Correct |
56 ms |
94316 KB |
Output is correct |
20 |
Correct |
54 ms |
94572 KB |
Output is correct |
21 |
Correct |
58 ms |
94588 KB |
Output is correct |
22 |
Correct |
71 ms |
94572 KB |
Output is correct |
23 |
Correct |
55 ms |
94572 KB |
Output is correct |
24 |
Correct |
56 ms |
94504 KB |
Output is correct |
25 |
Correct |
1824 ms |
371528 KB |
Output is correct |
26 |
Correct |
477 ms |
176284 KB |
Output is correct |
27 |
Runtime error |
1194 ms |
524292 KB |
Execution killed with signal 9 |
28 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
322 ms |
105976 KB |
Output is correct |
2 |
Correct |
341 ms |
106968 KB |
Output is correct |
3 |
Correct |
238 ms |
103144 KB |
Output is correct |
4 |
Correct |
344 ms |
107108 KB |
Output is correct |
5 |
Correct |
164 ms |
100072 KB |
Output is correct |
6 |
Correct |
329 ms |
106980 KB |
Output is correct |
7 |
Correct |
270 ms |
105316 KB |
Output is correct |
8 |
Correct |
335 ms |
106980 KB |
Output is correct |
9 |
Correct |
86 ms |
96236 KB |
Output is correct |
10 |
Correct |
332 ms |
106980 KB |
Output is correct |
11 |
Correct |
214 ms |
102252 KB |
Output is correct |
12 |
Correct |
316 ms |
106980 KB |
Output is correct |
13 |
Correct |
227 ms |
106724 KB |
Output is correct |
14 |
Correct |
216 ms |
106212 KB |
Output is correct |
15 |
Correct |
198 ms |
104988 KB |
Output is correct |
16 |
Correct |
207 ms |
104992 KB |
Output is correct |
17 |
Correct |
230 ms |
107108 KB |
Output is correct |
18 |
Correct |
212 ms |
105572 KB |
Output is correct |
19 |
Correct |
215 ms |
105832 KB |
Output is correct |
20 |
Correct |
214 ms |
105960 KB |
Output is correct |
21 |
Correct |
218 ms |
106724 KB |
Output is correct |
22 |
Correct |
217 ms |
105956 KB |
Output is correct |
23 |
Correct |
218 ms |
106084 KB |
Output is correct |
24 |
Correct |
200 ms |
105016 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
55 ms |
94316 KB |
Output is correct |
2 |
Correct |
57 ms |
94572 KB |
Output is correct |
3 |
Correct |
57 ms |
94700 KB |
Output is correct |
4 |
Correct |
56 ms |
94572 KB |
Output is correct |
5 |
Correct |
64 ms |
94444 KB |
Output is correct |
6 |
Correct |
55 ms |
94444 KB |
Output is correct |
7 |
Correct |
67 ms |
94720 KB |
Output is correct |
8 |
Correct |
66 ms |
94572 KB |
Output is correct |
9 |
Correct |
55 ms |
94444 KB |
Output is correct |
10 |
Correct |
63 ms |
94580 KB |
Output is correct |
11 |
Correct |
57 ms |
94444 KB |
Output is correct |
12 |
Correct |
63 ms |
94576 KB |
Output is correct |
13 |
Correct |
57 ms |
94444 KB |
Output is correct |
14 |
Correct |
58 ms |
94572 KB |
Output is correct |
15 |
Correct |
59 ms |
94572 KB |
Output is correct |
16 |
Correct |
56 ms |
94572 KB |
Output is correct |
17 |
Correct |
60 ms |
94572 KB |
Output is correct |
18 |
Correct |
55 ms |
94608 KB |
Output is correct |
19 |
Correct |
56 ms |
94316 KB |
Output is correct |
20 |
Correct |
54 ms |
94572 KB |
Output is correct |
21 |
Correct |
58 ms |
94588 KB |
Output is correct |
22 |
Correct |
71 ms |
94572 KB |
Output is correct |
23 |
Correct |
55 ms |
94572 KB |
Output is correct |
24 |
Correct |
56 ms |
94504 KB |
Output is correct |
25 |
Correct |
1824 ms |
371528 KB |
Output is correct |
26 |
Correct |
477 ms |
176284 KB |
Output is correct |
27 |
Runtime error |
1194 ms |
524292 KB |
Execution killed with signal 9 |
28 |
Halted |
0 ms |
0 KB |
- |