//#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define N 200015
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
struct Node{
int mx,mn,qmx,qmn,tag_mx,tag_mn,ans;
// ans is qmx-mn,mx-qmn
Node(int a=-1e18,int b=1e18,int c=-1e18,int d=1e18,int tag1=-1e18,int tag2=1e18,int e=-1e18):mx(a),mn(b),qmx(c),qmn(d),tag_mx(tag1),tag_mn(tag2),ans(e){}
int get_ans(){ return ans=max({ans,qmx-mn,mx-qmn}); }
void OUT(){
cout<<mx<<" "<<mn<<" "<<qmx<<" "<<qmn<<" "<<ans<<'\n';
}
};
struct segtree{
Node seg[4*N];
void add_tag(int i,int tag1,int tag2){
if (seg[i].tag_mx<tag1){
seg[i].tag_mx=tag1;
seg[i].qmx=tag1;
seg[i].get_ans();
}
if (seg[i].tag_mn>tag2){
seg[i].tag_mn=tag2;
seg[i].qmn=tag2;
seg[i].get_ans();
}
}
void push(int i){
add_tag(2*i,seg[i].tag_mx,seg[i].tag_mn);
add_tag(2*i+1,seg[i].tag_mx,seg[i].tag_mn);
seg[i].tag_mn=1e18; seg[i].tag_mx=-1e18;
}
Node merge(Node a,Node b){
Node ans=Node();
ans.mx=max(a.mx,b.mx);
ans.mn=min(a.mn,b.mn);
ans.ans=max(a.ans,b.ans);
return ans;
}
void change(int l,int r,int i,int pos,int val){ // 拔出現在放入的 r 並不在 pos 的區間內
if (l==r){
int tans=seg[i].ans;
seg[i]=Node(); seg[i].ans=tans;
if (val==0){
seg[i].mx=-1e18;
seg[i].mn=1e18;
}
else {
seg[i].mn=val;
seg[i].mx=val;
}
return;
}
int mid=(l+r)>>1; push(i);
if (pos<=mid) change(l,mid,2*i,pos,val);
else change(mid+1,r,2*i+1,pos,val);
seg[i]=merge(seg[2*i],seg[2*i+1]);
}
void modify(int l,int r,int i,int ll,int rr,int val){
if (ll>rr) return;
if (ll<=l&&rr>=r){
add_tag(i,val,val);
return;
}
int mid=(l+r)>>1; push(i);
if (rr<=mid) modify(l,mid,2*i,ll,rr,val);
else if (ll>mid) modify(mid+1,r,2*i+1,ll,rr,val);
else {
modify(l,mid,2*i,ll,rr,val);
modify(mid+1,r,2*i+1,ll,rr,val);
}
seg[i]=merge(seg[2*i],seg[2*i+1]);
}
int query(int l,int r,int i,int ll,int rr){
if (ll>rr) return -1e18;
if (ll<=l&&rr>=r)
return seg[i].ans;
int mid=(l+r)>>1; push(i);
if (rr<=mid) return query(l,mid,2*i,ll,rr);
else if (ll>mid) return query(mid+1,r,2*i+1,ll,rr);
else return max(query(l,mid,2*i,ll,rr),query(mid+1,r,2*i+1,ll,rr));
}
void debug(int l,int r,int i){
cout<<l<<" ~ "<<r<<" : ";
seg[i].OUT();
if (l==r){
return;
}
int mid=(l+r)>>1; push(i);
debug(l,mid,2*i); debug(mid+1,r,2*i+1);
}
}seg;
int n,h[N],a[N],b[N],q,ans[N];
vector<int>in[N],out[N];
vector<pii>qry[N];
signed main(){
fast
cin>>n;
for (int i=1;i<=n;i++){
cin>>h[i]>>a[i]>>b[i];
in[min(i+a[i],n+1)].push_back(i);
out[min(i+b[i],n+1)].push_back(i);
}
cin>>q;
for (int i=1;i<=q;i++){
int l,r; cin>>l>>r;
qry[r].push_back({l,i});
}
for (int i=1;i<=n;i++){
for (auto j:in[i]){
// cout<<"In "<<j<<" "<<h[j]<<'\n';
seg.change(1,n,1,j,h[j]);
}
// cout<<"modify "<<max(1LL,i-b[i])<<" "<<max(0LL,i-a[i])<<" "<<h[i]<<'\n';
seg.modify(1,n,1,max(1LL,i-b[i]),max(0LL,i-a[i]),h[i]);
// cout<<i<<" segtree : \n";
// seg.debug(1,n,1);
for (auto [l,j]:qry[i]){
ans[j]=seg.query(1,n,1,l,i);
// cout<<"query "<<l<<" "<<i<<" : "<<ans[j]<<'\n';
}
for (auto j:out[i]){
// cout<<"Out "<<j<<" "<<h[j]<<'\n';
seg.change(1,n,1,j,0);
}
}
for (int i=1;i<=q;i++)
cout<<max(ans[i],-1LL)<<'\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
58196 KB |
Output is correct |
2 |
Correct |
25 ms |
58324 KB |
Output is correct |
3 |
Correct |
31 ms |
58248 KB |
Output is correct |
4 |
Correct |
34 ms |
58188 KB |
Output is correct |
5 |
Correct |
30 ms |
58252 KB |
Output is correct |
6 |
Correct |
26 ms |
58324 KB |
Output is correct |
7 |
Correct |
26 ms |
58228 KB |
Output is correct |
8 |
Correct |
26 ms |
58300 KB |
Output is correct |
9 |
Correct |
26 ms |
58304 KB |
Output is correct |
10 |
Correct |
29 ms |
58296 KB |
Output is correct |
11 |
Correct |
27 ms |
58272 KB |
Output is correct |
12 |
Correct |
27 ms |
58280 KB |
Output is correct |
13 |
Correct |
28 ms |
58196 KB |
Output is correct |
14 |
Correct |
26 ms |
58252 KB |
Output is correct |
15 |
Correct |
27 ms |
58196 KB |
Output is correct |
16 |
Correct |
26 ms |
58268 KB |
Output is correct |
17 |
Correct |
26 ms |
58296 KB |
Output is correct |
18 |
Correct |
26 ms |
58196 KB |
Output is correct |
19 |
Correct |
26 ms |
58196 KB |
Output is correct |
20 |
Correct |
26 ms |
58300 KB |
Output is correct |
21 |
Correct |
30 ms |
58240 KB |
Output is correct |
22 |
Correct |
32 ms |
58312 KB |
Output is correct |
23 |
Correct |
29 ms |
58276 KB |
Output is correct |
24 |
Correct |
25 ms |
58212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
58196 KB |
Output is correct |
2 |
Correct |
25 ms |
58324 KB |
Output is correct |
3 |
Correct |
31 ms |
58248 KB |
Output is correct |
4 |
Correct |
34 ms |
58188 KB |
Output is correct |
5 |
Correct |
30 ms |
58252 KB |
Output is correct |
6 |
Correct |
26 ms |
58324 KB |
Output is correct |
7 |
Correct |
26 ms |
58228 KB |
Output is correct |
8 |
Correct |
26 ms |
58300 KB |
Output is correct |
9 |
Correct |
26 ms |
58304 KB |
Output is correct |
10 |
Correct |
29 ms |
58296 KB |
Output is correct |
11 |
Correct |
27 ms |
58272 KB |
Output is correct |
12 |
Correct |
27 ms |
58280 KB |
Output is correct |
13 |
Correct |
28 ms |
58196 KB |
Output is correct |
14 |
Correct |
26 ms |
58252 KB |
Output is correct |
15 |
Correct |
27 ms |
58196 KB |
Output is correct |
16 |
Correct |
26 ms |
58268 KB |
Output is correct |
17 |
Correct |
26 ms |
58296 KB |
Output is correct |
18 |
Correct |
26 ms |
58196 KB |
Output is correct |
19 |
Correct |
26 ms |
58196 KB |
Output is correct |
20 |
Correct |
26 ms |
58300 KB |
Output is correct |
21 |
Correct |
30 ms |
58240 KB |
Output is correct |
22 |
Correct |
32 ms |
58312 KB |
Output is correct |
23 |
Correct |
29 ms |
58276 KB |
Output is correct |
24 |
Correct |
25 ms |
58212 KB |
Output is correct |
25 |
Correct |
81 ms |
65240 KB |
Output is correct |
26 |
Correct |
34 ms |
59028 KB |
Output is correct |
27 |
Correct |
122 ms |
68260 KB |
Output is correct |
28 |
Correct |
106 ms |
68412 KB |
Output is correct |
29 |
Correct |
81 ms |
65460 KB |
Output is correct |
30 |
Correct |
99 ms |
64952 KB |
Output is correct |
31 |
Correct |
91 ms |
66984 KB |
Output is correct |
32 |
Correct |
115 ms |
68332 KB |
Output is correct |
33 |
Correct |
98 ms |
67752 KB |
Output is correct |
34 |
Correct |
66 ms |
63180 KB |
Output is correct |
35 |
Correct |
107 ms |
68272 KB |
Output is correct |
36 |
Correct |
110 ms |
68404 KB |
Output is correct |
37 |
Correct |
81 ms |
63560 KB |
Output is correct |
38 |
Correct |
153 ms |
67428 KB |
Output is correct |
39 |
Correct |
40 ms |
59608 KB |
Output is correct |
40 |
Correct |
103 ms |
67364 KB |
Output is correct |
41 |
Correct |
85 ms |
64940 KB |
Output is correct |
42 |
Correct |
103 ms |
67344 KB |
Output is correct |
43 |
Correct |
56 ms |
61364 KB |
Output is correct |
44 |
Correct |
117 ms |
67348 KB |
Output is correct |
45 |
Correct |
43 ms |
59888 KB |
Output is correct |
46 |
Correct |
109 ms |
67368 KB |
Output is correct |
47 |
Correct |
50 ms |
60588 KB |
Output is correct |
48 |
Correct |
116 ms |
67540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
300 ms |
70484 KB |
Output is correct |
2 |
Correct |
333 ms |
70848 KB |
Output is correct |
3 |
Correct |
237 ms |
67092 KB |
Output is correct |
4 |
Correct |
337 ms |
70280 KB |
Output is correct |
5 |
Correct |
153 ms |
64132 KB |
Output is correct |
6 |
Correct |
328 ms |
69824 KB |
Output is correct |
7 |
Correct |
290 ms |
67852 KB |
Output is correct |
8 |
Correct |
361 ms |
69776 KB |
Output is correct |
9 |
Correct |
62 ms |
60532 KB |
Output is correct |
10 |
Correct |
376 ms |
69864 KB |
Output is correct |
11 |
Correct |
223 ms |
65484 KB |
Output is correct |
12 |
Correct |
370 ms |
69796 KB |
Output is correct |
13 |
Correct |
193 ms |
67488 KB |
Output is correct |
14 |
Correct |
176 ms |
67628 KB |
Output is correct |
15 |
Correct |
190 ms |
67408 KB |
Output is correct |
16 |
Correct |
158 ms |
67680 KB |
Output is correct |
17 |
Correct |
189 ms |
67384 KB |
Output is correct |
18 |
Correct |
205 ms |
67544 KB |
Output is correct |
19 |
Correct |
181 ms |
67296 KB |
Output is correct |
20 |
Correct |
182 ms |
67832 KB |
Output is correct |
21 |
Correct |
184 ms |
67896 KB |
Output is correct |
22 |
Correct |
183 ms |
68212 KB |
Output is correct |
23 |
Correct |
186 ms |
67528 KB |
Output is correct |
24 |
Correct |
160 ms |
67936 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
58196 KB |
Output is correct |
2 |
Correct |
25 ms |
58324 KB |
Output is correct |
3 |
Correct |
31 ms |
58248 KB |
Output is correct |
4 |
Correct |
34 ms |
58188 KB |
Output is correct |
5 |
Correct |
30 ms |
58252 KB |
Output is correct |
6 |
Correct |
26 ms |
58324 KB |
Output is correct |
7 |
Correct |
26 ms |
58228 KB |
Output is correct |
8 |
Correct |
26 ms |
58300 KB |
Output is correct |
9 |
Correct |
26 ms |
58304 KB |
Output is correct |
10 |
Correct |
29 ms |
58296 KB |
Output is correct |
11 |
Correct |
27 ms |
58272 KB |
Output is correct |
12 |
Correct |
27 ms |
58280 KB |
Output is correct |
13 |
Correct |
28 ms |
58196 KB |
Output is correct |
14 |
Correct |
26 ms |
58252 KB |
Output is correct |
15 |
Correct |
27 ms |
58196 KB |
Output is correct |
16 |
Correct |
26 ms |
58268 KB |
Output is correct |
17 |
Correct |
26 ms |
58296 KB |
Output is correct |
18 |
Correct |
26 ms |
58196 KB |
Output is correct |
19 |
Correct |
26 ms |
58196 KB |
Output is correct |
20 |
Correct |
26 ms |
58300 KB |
Output is correct |
21 |
Correct |
30 ms |
58240 KB |
Output is correct |
22 |
Correct |
32 ms |
58312 KB |
Output is correct |
23 |
Correct |
29 ms |
58276 KB |
Output is correct |
24 |
Correct |
25 ms |
58212 KB |
Output is correct |
25 |
Correct |
81 ms |
65240 KB |
Output is correct |
26 |
Correct |
34 ms |
59028 KB |
Output is correct |
27 |
Correct |
122 ms |
68260 KB |
Output is correct |
28 |
Correct |
106 ms |
68412 KB |
Output is correct |
29 |
Correct |
81 ms |
65460 KB |
Output is correct |
30 |
Correct |
99 ms |
64952 KB |
Output is correct |
31 |
Correct |
91 ms |
66984 KB |
Output is correct |
32 |
Correct |
115 ms |
68332 KB |
Output is correct |
33 |
Correct |
98 ms |
67752 KB |
Output is correct |
34 |
Correct |
66 ms |
63180 KB |
Output is correct |
35 |
Correct |
107 ms |
68272 KB |
Output is correct |
36 |
Correct |
110 ms |
68404 KB |
Output is correct |
37 |
Correct |
81 ms |
63560 KB |
Output is correct |
38 |
Correct |
153 ms |
67428 KB |
Output is correct |
39 |
Correct |
40 ms |
59608 KB |
Output is correct |
40 |
Correct |
103 ms |
67364 KB |
Output is correct |
41 |
Correct |
85 ms |
64940 KB |
Output is correct |
42 |
Correct |
103 ms |
67344 KB |
Output is correct |
43 |
Correct |
56 ms |
61364 KB |
Output is correct |
44 |
Correct |
117 ms |
67348 KB |
Output is correct |
45 |
Correct |
43 ms |
59888 KB |
Output is correct |
46 |
Correct |
109 ms |
67368 KB |
Output is correct |
47 |
Correct |
50 ms |
60588 KB |
Output is correct |
48 |
Correct |
116 ms |
67540 KB |
Output is correct |
49 |
Correct |
300 ms |
70484 KB |
Output is correct |
50 |
Correct |
333 ms |
70848 KB |
Output is correct |
51 |
Correct |
237 ms |
67092 KB |
Output is correct |
52 |
Correct |
337 ms |
70280 KB |
Output is correct |
53 |
Correct |
153 ms |
64132 KB |
Output is correct |
54 |
Correct |
328 ms |
69824 KB |
Output is correct |
55 |
Correct |
290 ms |
67852 KB |
Output is correct |
56 |
Correct |
361 ms |
69776 KB |
Output is correct |
57 |
Correct |
62 ms |
60532 KB |
Output is correct |
58 |
Correct |
376 ms |
69864 KB |
Output is correct |
59 |
Correct |
223 ms |
65484 KB |
Output is correct |
60 |
Correct |
370 ms |
69796 KB |
Output is correct |
61 |
Correct |
193 ms |
67488 KB |
Output is correct |
62 |
Correct |
176 ms |
67628 KB |
Output is correct |
63 |
Correct |
190 ms |
67408 KB |
Output is correct |
64 |
Correct |
158 ms |
67680 KB |
Output is correct |
65 |
Correct |
189 ms |
67384 KB |
Output is correct |
66 |
Correct |
205 ms |
67544 KB |
Output is correct |
67 |
Correct |
181 ms |
67296 KB |
Output is correct |
68 |
Correct |
182 ms |
67832 KB |
Output is correct |
69 |
Correct |
184 ms |
67896 KB |
Output is correct |
70 |
Correct |
183 ms |
68212 KB |
Output is correct |
71 |
Correct |
186 ms |
67528 KB |
Output is correct |
72 |
Correct |
160 ms |
67936 KB |
Output is correct |
73 |
Correct |
471 ms |
79992 KB |
Output is correct |
74 |
Correct |
373 ms |
73976 KB |
Output is correct |
75 |
Correct |
439 ms |
79668 KB |
Output is correct |
76 |
Correct |
632 ms |
84312 KB |
Output is correct |
77 |
Correct |
277 ms |
72916 KB |
Output is correct |
78 |
Correct |
551 ms |
80640 KB |
Output is correct |
79 |
Correct |
573 ms |
82252 KB |
Output is correct |
80 |
Correct |
608 ms |
84304 KB |
Output is correct |
81 |
Correct |
197 ms |
70868 KB |
Output is correct |
82 |
Correct |
477 ms |
78648 KB |
Output is correct |
83 |
Correct |
403 ms |
78464 KB |
Output is correct |
84 |
Correct |
569 ms |
84304 KB |
Output is correct |
85 |
Correct |
294 ms |
76748 KB |
Output is correct |
86 |
Correct |
387 ms |
81116 KB |
Output is correct |
87 |
Correct |
221 ms |
72424 KB |
Output is correct |
88 |
Correct |
422 ms |
81636 KB |
Output is correct |
89 |
Correct |
326 ms |
78312 KB |
Output is correct |
90 |
Correct |
359 ms |
81512 KB |
Output is correct |
91 |
Correct |
245 ms |
74168 KB |
Output is correct |
92 |
Correct |
391 ms |
80968 KB |
Output is correct |
93 |
Correct |
264 ms |
72852 KB |
Output is correct |
94 |
Correct |
419 ms |
81084 KB |
Output is correct |
95 |
Correct |
260 ms |
73600 KB |
Output is correct |
96 |
Correct |
415 ms |
81040 KB |
Output is correct |