#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 < int > out2[200005];
vector < int > in2[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]++;
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)
{
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) 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)
{
out[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:out[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:91:13: warning: unused variable 'ok' [-Wunused-variable]
91 | int N,M,ok=0,i,j;
| ^~
antennas.cpp:92:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
92 | scanf("%d",&N);
| ~~~~~^~~~~~~~~
antennas.cpp:95:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
95 | scanf("%d %d %d",&all[i],&l[i],&r[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:102:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
102 | scanf("%d",&M);
| ~~~~~^~~~~~~~~
antennas.cpp:105:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
105 | scanf("%d %d",&x[i],&y[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
62 ms |
94444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
62 ms |
94444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
388 ms |
117220 KB |
Output is correct |
| 2 |
Correct |
424 ms |
119608 KB |
Output is correct |
| 3 |
Correct |
296 ms |
111976 KB |
Output is correct |
| 4 |
Correct |
455 ms |
119396 KB |
Output is correct |
| 5 |
Correct |
198 ms |
105960 KB |
Output is correct |
| 6 |
Correct |
436 ms |
119396 KB |
Output is correct |
| 7 |
Correct |
362 ms |
116196 KB |
Output is correct |
| 8 |
Correct |
479 ms |
119524 KB |
Output is correct |
| 9 |
Correct |
105 ms |
98284 KB |
Output is correct |
| 10 |
Correct |
417 ms |
119396 KB |
Output is correct |
| 11 |
Correct |
288 ms |
110188 KB |
Output is correct |
| 12 |
Correct |
423 ms |
119492 KB |
Output is correct |
| 13 |
Correct |
253 ms |
119140 KB |
Output is correct |
| 14 |
Correct |
246 ms |
118756 KB |
Output is correct |
| 15 |
Correct |
233 ms |
117592 KB |
Output is correct |
| 16 |
Correct |
240 ms |
117408 KB |
Output is correct |
| 17 |
Correct |
261 ms |
119652 KB |
Output is correct |
| 18 |
Correct |
257 ms |
118116 KB |
Output is correct |
| 19 |
Correct |
248 ms |
118376 KB |
Output is correct |
| 20 |
Correct |
256 ms |
118760 KB |
Output is correct |
| 21 |
Correct |
251 ms |
119140 KB |
Output is correct |
| 22 |
Correct |
250 ms |
118536 KB |
Output is correct |
| 23 |
Correct |
277 ms |
118756 KB |
Output is correct |
| 24 |
Correct |
231 ms |
117560 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
62 ms |
94444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
