#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4")
#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
const int mxn = 2e5+10;
const ll inf = 1e9+10;
#define ls now*2+1
#define rs now*2+2
#define mid ((l+r)>>1)
struct SEG1{
struct node{
int mn,mx,val;
node(){
mn = inf,mx = 0,val = -1;
}
};
node seg[mxn*4];
SEG1(){}
node pull(node a,node b){
node re;
re.mn = min(a.mn,b.mn);
re.mx = 0;
re.val = max(a.val,b.val);
return re;
}
void push(int now,int l,int r){
seg[ls].mx = max(seg[ls].mx,seg[now].mx);
seg[rs].mx = max(seg[rs].mx,seg[now].mx);
seg[ls].val = max(seg[ls].val,seg[ls].mx-seg[ls].mn);
seg[rs].val = max(seg[rs].val,seg[rs].mx-seg[rs].mn);
seg[now].mx = 0;
return;
}
void chmax(int now,int l,int r,int s,int e,int v){
if(l>=s&&e>=r){
seg[now].mx = max(seg[now].mx,v);
seg[now].val = max(seg[now].val,seg[now].mx-seg[now].mn);
return;
}
if(mid>=s)chmax(ls,l,mid,s,e,v);
if(mid<e)chmax(rs,mid+1,r,s,e,v);
seg[now].mn = min(seg[ls].mn,seg[rs].mn);
seg[now].val = max(seg[ls].val,seg[rs].val);
return;
}
void chmin(int now,int l,int r,int p,int v){
if(l == r){
seg[now].mn = v;
seg[now].val = seg[now].mx-seg[now].mn;
return;
}
push(now,l,r);
if(mid>=p)chmin(ls,l,mid,p,v);
else chmin(rs,mid+1,r,p,v);
seg[now] = pull(seg[ls],seg[rs]);
return;
}
node getval(int now,int l,int r,int s,int e){
if(l>=s&&e>=r)return seg[now];
push(now,l,r);
if(mid>=e)return getval(ls,l,mid,s,e);
else if(mid<s)return getval(rs,mid+1,r,s,e);
else return pull(getval(ls,l,mid,s,e),getval(rs,mid+1,r,s,e));
}
void init(){
for(auto &i:seg)i.mn = inf,i.mx = 0,i.val = -1;
return;
}
};
struct SEG2{
int seg[mxn*4];
SEG2(){
for(auto &i:seg)i = -1;
}
void modify(int now,int l,int r,int p,int v){
if(l == r){
seg[now] = v;
return;
}
if(mid>=p)modify(ls,l,mid,p,v);
else modify(rs,mid+1,r,p,v);
seg[now] = max(seg[ls],seg[rs]);
return;
}
int getval(int now,int l,int r,int s,int e){
if(l>=s&&e>=r)return seg[now];
if(mid>=e)return getval(ls,l,mid,s,e);
else if(mid<s)return getval(rs,mid+1,r,s,e);
else return max(getval(ls,l,mid,s,e),getval(rs,mid+1,r,s,e));
}
void init(){
for(auto &i:seg)i = -1;
return;
}
};
#undef ls
#undef rs
#undef mid
struct D{
int tp,id,pos;
D(){}
D(int tt,int ii,int pp):tp(tt),id(ii),pos(pp){}
bool operator<(D b)const{
return pos == b.pos?tp<b.tp:pos<b.pos;
}
};
SEG1 seg1;
SEG2 seg2;
pii req[mxn];
pii range[mxn];
int H[mxn];
int N,Q;
vector<D> op;
int ans[mxn];
void solve(){
op.clear();
seg1.init();
seg2.init();
for(int i = 1;i<=N;i++){
int pl = i+range[i].fs,pr = i+range[i].sc+1;
pl = min(pl,N),pr = min(pr,N+1);
op.push_back(D(1,i,pr));
op.push_back(D(2,i,pl));
op.push_back(D(3,i,i));
}
for(int i = 1;i<=Q;i++){
op.push_back(D(4,i,req[i].sc));
}
sort(op.begin(),op.end());
for(auto &[tp,id,___]:op){
//cout<<tp<<':'<<id<<' '<<___<<"::"<<seg1.seg[0].val<<endl;
if(tp == 1){
seg2.modify(0,0,N,id,seg1.getval(0,0,N,id,id).val);
seg1.chmin(0,0,N,id,inf);
}
else if(tp == 2){
seg1.chmin(0,0,N,id,H[id]);
}
else if(tp == 3){
int pl = id-range[id].sc,pr = id-range[id].fs;
pl = max(pl,0),pr = max(pr,0);
seg1.chmax(0,0,N,pl,pr,H[id]);
}
else{
ans[id] = max({ans[id],seg1.getval(0,0,N,req[id].fs,req[id].sc).val,seg2.getval(0,0,N,req[id].fs,req[id].sc)});
}
}
//cout<<endl;
return;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>N;
for(int i = 1;i<=N;i++){
cin>>H[i]>>range[i].fs>>range[i].sc;
}
cin>>Q;
for(int i = 1;i<=Q;i++){
cin>>req[i].fs>>req[i].sc;
}
memset(ans,-1,sizeof(ans));
solve();
reverse(H+1,H+N+1);
reverse(range+1,range+N+1);
for(int i = 1;i<=Q;i++){
req[i].fs = N+1-req[i].fs,req[i].sc = N+1-req[i].sc;
swap(req[i].fs,req[i].sc);
}
solve();
for(int i = 1;i<=Q;i++){
cout<<ans[i]<<'\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
17496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
17496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
371 ms |
30412 KB |
Output is correct |
| 2 |
Correct |
401 ms |
31424 KB |
Output is correct |
| 3 |
Incorrect |
271 ms |
24528 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
17496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
