#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define sz(x) (int)(x.size())
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define vi vector<int>
#define vp vector<pii>
#define vvi vector<vi>
//Don't open the standings during contests.
const int mxn=2e5+5;
vector<pii>ask(mxn);
vector<int>add2[mxn];
vector<int>remove2[mxn];
vector<int>add[mxn];
vector<int>remov[mxn];
vector<int>h(mxn),a(mxn),b(mxn),ans(mxn);
set<int>nowq;
int mx[4*mxn],mn[4*mxn];
void modify(int l,int r,int id,int p,int v){
if(l==r){
mx[id]=mn[id]=v;
return;
}
int mm=l+r>>1;
if(p<=mm){
modify(l,mm,id*2,p,v);
}
else{
modify(mm+1,r,id*2+1,p,v);
}
mx[id]=max(mx[id*2],mx[id*2+1]);
if(!mn[id*2] or !mn[id*2+1])mn[id]=mn[id*2]?mn[id*2]:mn[id*2+1];
else mn[id]=min(mn[id*2],mn[id*2+1]);
}
pii query(int l,int r,int id,int ql,int qr){
if(ql>qr or l>r)return {0,0};
if(ql<=l and r<=qr){
return {mx[id],mn[id]};
}
int mm=l+r>>1;
if(qr<=mm){
return query(l,mm,id*2,ql,qr);
}
else if(ql>mm){
return query(mm+1,r,id*2+1,ql,qr);
}
else{
pii a=query(l,mm,id*2,ql,mm);
pii b=query(mm+1,r,id*2+1,mm+1,qr);
return {max(a.F,b.F),min(a.S,b.S)};
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>h[i]>>a[i]>>b[i];
}
int q;
cin>>q;
for(int i=1;i<=q;i++){
ans[i]=-1;
int l,r;
cin>>l>>r;
ask[i]={l,r};
add2[l].pb(i);
remove2[r].pb(i);
}
for(int i=1;i<=n;i++){
for(auto j:add2[i])nowq.insert(j);
for(auto j:add[i])modify(1,n,1,j,h[j]);
if(i+a[i]<=n)add[i+a[i]].pb(i);
if(i+b[i]<=n)remov[i+b[i]].pb(i);
for(auto it=nowq.begin();it!=nowq.end();it++){
pii q=query(1,n,1,max({1LL,i-b[i],ask[*it].F}),i-a[i]);
if(q.F)chmax(ans[*it],abs(q.F-h[i]));
if(q.S)chmax(ans[*it],abs(h[i]-q.S));
}
for(auto j:remov[i])modify(1,n,1,j,0);
for(auto j:remove2[i])nowq.erase(j);
}
for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';
}
/*
input:
掃描線
從1掃到N
如果當前有詢問
chmax(ans[j],max(h[i]-min(i-a[i]~i-b[i]),max(i-a[i]~i-b[i]-h[i]));
*/
Compilation message
antennas.cpp: In function 'void modify(long long int, long long int, long long int, long long int, long long int)':
antennas.cpp:30:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
30 | int mm=l+r>>1;
| ~^~
antennas.cpp: In function 'std::pair<long long int, long long int> query(long long int, long long int, long long int, long long int, long long int)':
antennas.cpp:46:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
46 | int mm=l+r>>1;
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
28504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
28504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
115 ms |
40196 KB |
Output is correct |
| 2 |
Incorrect |
139 ms |
40528 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
28504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
