#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef unsigned long long ull;
typedef long double ld;
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;
int h[255555];
int a[255555];
int b[255555];
int ans[255555];
vector<ii> Q[255555];
const int INF = int(2e9)+20;
struct node
{
int mx;
int minc;
int lazyx;
node(int _mx=-INF,int _minc=INF,int _lazyx=-INF):mx(_mx),minc(_minc),lazyx(_lazyx){};
};
node st[255555*4];
void reset()
{
for(int i=0;i<255555*4;i++) st[i]=node();
}
void combine(int id)
{
st[id].mx=max(st[id*2].mx,st[id*2+1].mx);
st[id].minc=min(st[id*2].minc,st[id*2+1].minc);
}
void push(int id, int l, int r)
{
if(st[id].lazyx!=-INF)
{
st[id].mx=max(st[id].mx,st[id].lazyx-st[id].minc);
if(r-l>=2)
{
st[id*2].lazyx=max(st[id*2].lazyx,st[id].lazyx);
st[id*2+1].lazyx=max(st[id*2+1].lazyx,st[id].lazyx);
}
st[id].lazyx=-INF;
}
}
void update(int id, int l, int r, int pos, int newc)
{
push(id,l,r);
if(pos>=r||pos<l) return ;
if(r-l<2)
{
st[id].minc=newc;
return ;
}
int mid=(l+r)>>1;
update(id*2,l,mid,pos,newc); update(id*2+1,mid,r,pos,newc);
combine(id);
}
void amax(int id, int l, int r, int ql, int qr, int v)
{
push(id,l,r);
if(ql>=r||l>=qr) return ;
if(ql<=l&&r<=qr)
{
st[id].lazyx=v;
push(id,l,r);
return ;
}
int mid=(l+r)>>1;
amax(id*2,l,mid,ql,qr,v); amax(id*2+1,mid,r,ql,qr,v);
combine(id);
}
int query(int id, int l, int r, int ql, int qr)
{
push(id,l,r);
if(ql>=r||l>=qr) return -INF;
if(ql<=l&&r<=qr) return st[id].mx;
int mid=(l+r)>>1;
return max(query(id*2,l,mid,ql,qr),query(id*2+1,mid,r,ql,qr));
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
int n; cin>>n;
for(int i=0;i<n;i++)
{
cin>>h[i]>>a[i]>>b[i];
}
int q; cin>>q;
vector<pair<ii,int> > queries;
for(int i=0;i<q;i++)
{
int l,r; cin>>l>>r; l--; r--;
queries.pb({{l,r},i});
ans[i]=-1;
}
for(int loop=0;loop<2;loop++)
{
for(int i=0;i<n;i++) Q[i].clear();
for(int i=0;i<q;i++)
{
Q[queries[i].fi.se].pb(mp(queries[i].fi.fi,i));
}
vector<pair<int,ii> > events;
for(int i=0;i<n;i++)
{
events.pb(mp(i+a[i],mp(i,1)));
events.pb(mp(i+b[i]+1,mp(i,-1)));
}
int ptr=0;
reset();
sort(events.begin(),events.end());
for(int i=0;i<n;i++)
{
int L=i-b[i]; int R=i-a[i];
L=max(L,0); R=max(R,-1);
while(ptr<events.size()&&events[ptr].fi<=i)
{
if(events[ptr].se.se==-1)
{
update(1,0,n,events[ptr].se.fi,INF);
}
else
{
update(1,0,n,events[ptr].se.fi,h[events[ptr].se.fi]);
}
ptr++;
}
amax(1,0,n,L,R+1,h[i]);
for(ii v:Q[i])
{
ans[v.se]=max(ans[v.se],query(1,0,n,v.fi,i+1));
}
}
reverse(h,h+n);
reverse(a,a+n);
reverse(b,b+n);
for(int i=0;i<queries.size();i++)
{
queries[i].fi.fi=n-1-queries[i].fi.fi;
queries[i].fi.se=n-1-queries[i].fi.se;
swap(queries[i].fi.fi,queries[i].fi.se);
}
}
for(int i=0;i<q;i++)
{
cout<<ans[i]<<'\n';
}
}
Compilation message
antennas.cpp: In function 'int main()':
antennas.cpp:138:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ptr<events.size()&&events[ptr].fi<=i)
~~~^~~~~~~~~~~~~~
antennas.cpp:159:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<queries.size();i++)
~^~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
18424 KB |
Output is correct |
2 |
Correct |
21 ms |
18304 KB |
Output is correct |
3 |
Correct |
19 ms |
18424 KB |
Output is correct |
4 |
Correct |
22 ms |
18432 KB |
Output is correct |
5 |
Correct |
20 ms |
18432 KB |
Output is correct |
6 |
Correct |
21 ms |
18432 KB |
Output is correct |
7 |
Correct |
24 ms |
18432 KB |
Output is correct |
8 |
Correct |
20 ms |
18432 KB |
Output is correct |
9 |
Correct |
20 ms |
18340 KB |
Output is correct |
10 |
Correct |
25 ms |
18432 KB |
Output is correct |
11 |
Correct |
21 ms |
18412 KB |
Output is correct |
12 |
Correct |
22 ms |
18480 KB |
Output is correct |
13 |
Correct |
20 ms |
18432 KB |
Output is correct |
14 |
Correct |
20 ms |
18432 KB |
Output is correct |
15 |
Correct |
21 ms |
18432 KB |
Output is correct |
16 |
Correct |
20 ms |
18432 KB |
Output is correct |
17 |
Correct |
20 ms |
18404 KB |
Output is correct |
18 |
Correct |
25 ms |
18424 KB |
Output is correct |
19 |
Correct |
22 ms |
18424 KB |
Output is correct |
20 |
Correct |
21 ms |
18424 KB |
Output is correct |
21 |
Correct |
21 ms |
18432 KB |
Output is correct |
22 |
Correct |
22 ms |
18432 KB |
Output is correct |
23 |
Correct |
25 ms |
18424 KB |
Output is correct |
24 |
Correct |
24 ms |
18432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
18424 KB |
Output is correct |
2 |
Correct |
21 ms |
18304 KB |
Output is correct |
3 |
Correct |
19 ms |
18424 KB |
Output is correct |
4 |
Correct |
22 ms |
18432 KB |
Output is correct |
5 |
Correct |
20 ms |
18432 KB |
Output is correct |
6 |
Correct |
21 ms |
18432 KB |
Output is correct |
7 |
Correct |
24 ms |
18432 KB |
Output is correct |
8 |
Correct |
20 ms |
18432 KB |
Output is correct |
9 |
Correct |
20 ms |
18340 KB |
Output is correct |
10 |
Correct |
25 ms |
18432 KB |
Output is correct |
11 |
Correct |
21 ms |
18412 KB |
Output is correct |
12 |
Correct |
22 ms |
18480 KB |
Output is correct |
13 |
Correct |
20 ms |
18432 KB |
Output is correct |
14 |
Correct |
20 ms |
18432 KB |
Output is correct |
15 |
Correct |
21 ms |
18432 KB |
Output is correct |
16 |
Correct |
20 ms |
18432 KB |
Output is correct |
17 |
Correct |
20 ms |
18404 KB |
Output is correct |
18 |
Correct |
25 ms |
18424 KB |
Output is correct |
19 |
Correct |
22 ms |
18424 KB |
Output is correct |
20 |
Correct |
21 ms |
18424 KB |
Output is correct |
21 |
Correct |
21 ms |
18432 KB |
Output is correct |
22 |
Correct |
22 ms |
18432 KB |
Output is correct |
23 |
Correct |
25 ms |
18424 KB |
Output is correct |
24 |
Correct |
24 ms |
18432 KB |
Output is correct |
25 |
Correct |
158 ms |
29788 KB |
Output is correct |
26 |
Correct |
41 ms |
19828 KB |
Output is correct |
27 |
Correct |
227 ms |
34088 KB |
Output is correct |
28 |
Correct |
253 ms |
33732 KB |
Output is correct |
29 |
Correct |
159 ms |
30040 KB |
Output is correct |
30 |
Correct |
173 ms |
29176 KB |
Output is correct |
31 |
Correct |
240 ms |
32700 KB |
Output is correct |
32 |
Correct |
267 ms |
33904 KB |
Output is correct |
33 |
Correct |
211 ms |
33440 KB |
Output is correct |
34 |
Correct |
130 ms |
25952 KB |
Output is correct |
35 |
Correct |
249 ms |
34564 KB |
Output is correct |
36 |
Correct |
313 ms |
33804 KB |
Output is correct |
37 |
Correct |
140 ms |
26952 KB |
Output is correct |
38 |
Correct |
241 ms |
32860 KB |
Output is correct |
39 |
Correct |
53 ms |
20720 KB |
Output is correct |
40 |
Correct |
236 ms |
32700 KB |
Output is correct |
41 |
Correct |
175 ms |
29580 KB |
Output is correct |
42 |
Correct |
261 ms |
32820 KB |
Output is correct |
43 |
Correct |
89 ms |
23528 KB |
Output is correct |
44 |
Correct |
258 ms |
32748 KB |
Output is correct |
45 |
Correct |
65 ms |
21144 KB |
Output is correct |
46 |
Correct |
214 ms |
32960 KB |
Output is correct |
47 |
Correct |
69 ms |
22248 KB |
Output is correct |
48 |
Correct |
272 ms |
32936 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
545 ms |
45452 KB |
Output is correct |
2 |
Correct |
804 ms |
47160 KB |
Output is correct |
3 |
Correct |
432 ms |
42224 KB |
Output is correct |
4 |
Correct |
649 ms |
47028 KB |
Output is correct |
5 |
Correct |
323 ms |
32028 KB |
Output is correct |
6 |
Correct |
548 ms |
47028 KB |
Output is correct |
7 |
Correct |
526 ms |
44900 KB |
Output is correct |
8 |
Correct |
645 ms |
47064 KB |
Output is correct |
9 |
Correct |
88 ms |
22496 KB |
Output is correct |
10 |
Correct |
627 ms |
47028 KB |
Output is correct |
11 |
Correct |
328 ms |
34792 KB |
Output is correct |
12 |
Correct |
643 ms |
47064 KB |
Output is correct |
13 |
Correct |
348 ms |
46904 KB |
Output is correct |
14 |
Correct |
348 ms |
47028 KB |
Output is correct |
15 |
Correct |
329 ms |
46916 KB |
Output is correct |
16 |
Correct |
312 ms |
46960 KB |
Output is correct |
17 |
Correct |
362 ms |
47076 KB |
Output is correct |
18 |
Correct |
341 ms |
46824 KB |
Output is correct |
19 |
Correct |
420 ms |
46832 KB |
Output is correct |
20 |
Correct |
393 ms |
46832 KB |
Output is correct |
21 |
Correct |
383 ms |
47020 KB |
Output is correct |
22 |
Correct |
394 ms |
46856 KB |
Output is correct |
23 |
Correct |
397 ms |
46920 KB |
Output is correct |
24 |
Correct |
369 ms |
46856 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
18424 KB |
Output is correct |
2 |
Correct |
21 ms |
18304 KB |
Output is correct |
3 |
Correct |
19 ms |
18424 KB |
Output is correct |
4 |
Correct |
22 ms |
18432 KB |
Output is correct |
5 |
Correct |
20 ms |
18432 KB |
Output is correct |
6 |
Correct |
21 ms |
18432 KB |
Output is correct |
7 |
Correct |
24 ms |
18432 KB |
Output is correct |
8 |
Correct |
20 ms |
18432 KB |
Output is correct |
9 |
Correct |
20 ms |
18340 KB |
Output is correct |
10 |
Correct |
25 ms |
18432 KB |
Output is correct |
11 |
Correct |
21 ms |
18412 KB |
Output is correct |
12 |
Correct |
22 ms |
18480 KB |
Output is correct |
13 |
Correct |
20 ms |
18432 KB |
Output is correct |
14 |
Correct |
20 ms |
18432 KB |
Output is correct |
15 |
Correct |
21 ms |
18432 KB |
Output is correct |
16 |
Correct |
20 ms |
18432 KB |
Output is correct |
17 |
Correct |
20 ms |
18404 KB |
Output is correct |
18 |
Correct |
25 ms |
18424 KB |
Output is correct |
19 |
Correct |
22 ms |
18424 KB |
Output is correct |
20 |
Correct |
21 ms |
18424 KB |
Output is correct |
21 |
Correct |
21 ms |
18432 KB |
Output is correct |
22 |
Correct |
22 ms |
18432 KB |
Output is correct |
23 |
Correct |
25 ms |
18424 KB |
Output is correct |
24 |
Correct |
24 ms |
18432 KB |
Output is correct |
25 |
Correct |
158 ms |
29788 KB |
Output is correct |
26 |
Correct |
41 ms |
19828 KB |
Output is correct |
27 |
Correct |
227 ms |
34088 KB |
Output is correct |
28 |
Correct |
253 ms |
33732 KB |
Output is correct |
29 |
Correct |
159 ms |
30040 KB |
Output is correct |
30 |
Correct |
173 ms |
29176 KB |
Output is correct |
31 |
Correct |
240 ms |
32700 KB |
Output is correct |
32 |
Correct |
267 ms |
33904 KB |
Output is correct |
33 |
Correct |
211 ms |
33440 KB |
Output is correct |
34 |
Correct |
130 ms |
25952 KB |
Output is correct |
35 |
Correct |
249 ms |
34564 KB |
Output is correct |
36 |
Correct |
313 ms |
33804 KB |
Output is correct |
37 |
Correct |
140 ms |
26952 KB |
Output is correct |
38 |
Correct |
241 ms |
32860 KB |
Output is correct |
39 |
Correct |
53 ms |
20720 KB |
Output is correct |
40 |
Correct |
236 ms |
32700 KB |
Output is correct |
41 |
Correct |
175 ms |
29580 KB |
Output is correct |
42 |
Correct |
261 ms |
32820 KB |
Output is correct |
43 |
Correct |
89 ms |
23528 KB |
Output is correct |
44 |
Correct |
258 ms |
32748 KB |
Output is correct |
45 |
Correct |
65 ms |
21144 KB |
Output is correct |
46 |
Correct |
214 ms |
32960 KB |
Output is correct |
47 |
Correct |
69 ms |
22248 KB |
Output is correct |
48 |
Correct |
272 ms |
32936 KB |
Output is correct |
49 |
Correct |
545 ms |
45452 KB |
Output is correct |
50 |
Correct |
804 ms |
47160 KB |
Output is correct |
51 |
Correct |
432 ms |
42224 KB |
Output is correct |
52 |
Correct |
649 ms |
47028 KB |
Output is correct |
53 |
Correct |
323 ms |
32028 KB |
Output is correct |
54 |
Correct |
548 ms |
47028 KB |
Output is correct |
55 |
Correct |
526 ms |
44900 KB |
Output is correct |
56 |
Correct |
645 ms |
47064 KB |
Output is correct |
57 |
Correct |
88 ms |
22496 KB |
Output is correct |
58 |
Correct |
627 ms |
47028 KB |
Output is correct |
59 |
Correct |
328 ms |
34792 KB |
Output is correct |
60 |
Correct |
643 ms |
47064 KB |
Output is correct |
61 |
Correct |
348 ms |
46904 KB |
Output is correct |
62 |
Correct |
348 ms |
47028 KB |
Output is correct |
63 |
Correct |
329 ms |
46916 KB |
Output is correct |
64 |
Correct |
312 ms |
46960 KB |
Output is correct |
65 |
Correct |
362 ms |
47076 KB |
Output is correct |
66 |
Correct |
341 ms |
46824 KB |
Output is correct |
67 |
Correct |
420 ms |
46832 KB |
Output is correct |
68 |
Correct |
393 ms |
46832 KB |
Output is correct |
69 |
Correct |
383 ms |
47020 KB |
Output is correct |
70 |
Correct |
394 ms |
46856 KB |
Output is correct |
71 |
Correct |
397 ms |
46920 KB |
Output is correct |
72 |
Correct |
369 ms |
46856 KB |
Output is correct |
73 |
Correct |
1100 ms |
57900 KB |
Output is correct |
74 |
Correct |
735 ms |
48576 KB |
Output is correct |
75 |
Correct |
870 ms |
58080 KB |
Output is correct |
76 |
Correct |
1037 ms |
63516 KB |
Output is correct |
77 |
Correct |
691 ms |
43660 KB |
Output is correct |
78 |
Correct |
878 ms |
58488 KB |
Output is correct |
79 |
Correct |
1055 ms |
61204 KB |
Output is correct |
80 |
Correct |
1067 ms |
63472 KB |
Output is correct |
81 |
Correct |
431 ms |
39000 KB |
Output is correct |
82 |
Correct |
1012 ms |
55556 KB |
Output is correct |
83 |
Correct |
835 ms |
50604 KB |
Output is correct |
84 |
Correct |
1207 ms |
63540 KB |
Output is correct |
85 |
Correct |
674 ms |
56900 KB |
Output is correct |
86 |
Correct |
872 ms |
63472 KB |
Output is correct |
87 |
Correct |
459 ms |
49644 KB |
Output is correct |
88 |
Correct |
851 ms |
63500 KB |
Output is correct |
89 |
Correct |
859 ms |
59444 KB |
Output is correct |
90 |
Correct |
904 ms |
63496 KB |
Output is correct |
91 |
Correct |
571 ms |
53152 KB |
Output is correct |
92 |
Correct |
962 ms |
63460 KB |
Output is correct |
93 |
Correct |
417 ms |
50116 KB |
Output is correct |
94 |
Correct |
854 ms |
63416 KB |
Output is correct |
95 |
Correct |
482 ms |
51772 KB |
Output is correct |
96 |
Correct |
760 ms |
63404 KB |
Output is correct |