#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sortvec(x) sort(all(x))
#define compress(x) x.erase(unique(all(x)), x.end())
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
const LL llinf=987654321987654321;
const int inf=2000000000;
struct SEGMENT_TREE{
LL tree[800010], h[800010], lazy[800010];
void init(){
for(int i=1; i<800000; i++){
tree[i]=lazy[i]=-llinf;
h[i]=llinf;
}
}
void propogate(int point){
lazy[point*2]=max(lazy[point], lazy[point*2]);
lazy[point*2+1]=max(lazy[point], lazy[point*2+1]);
tree[point*2]=max(tree[point*2], lazy[point]-h[point*2]);
tree[point*2+1]=max(tree[point*2+1], lazy[point]-h[point*2+1]);
tree[point]=max(max(tree[point*2], tree[point*2+1]), tree[point]);
lazy[point]=-llinf;
}
void update(int point, int s, int e, int num, LL qu){
if(s==e){
h[point]=qu;
return;
}
propogate(point);
int mid=(s+e)/2;
if(num<=mid)update(point*2, s, mid, num, qu);
else update(point*2+1, mid+1, e, num, qu);
tree[point]=max(tree[point*2], tree[point*2+1]);
h[point]=min(h[point*2], h[point*2+1]);
}
void alter(int point, int s, int e, int a, int b, LL qu){
if(e<a||s>b)return;
if(a<=s&&e<=b){
if(s!=e)propogate(point);
lazy[point]=qu;
tree[point]=max(tree[point], qu-h[point]);
return;
}
int mid=(s+e)/2;
propogate(point);
alter(point*2, s, mid, a, b, qu);
alter(point*2+1, mid+1, e, a, b, qu);
tree[point]=max(tree[point*2], tree[point*2+1]);
h[point]=min(h[point*2], h[point*2+1]);
}
LL query(int point, int s, int e, int a, int b){
if(e<a||s>b)return -llinf;
if(s!=e)propogate(point);
if(a<=s&&e<=b)return tree[point];
int mid=(s+e)/2;
LL ret=max(query(point*2, s, mid, a, b), query(point*2+1, mid+1, e, a, b));
tree[point]=max(tree[point*2], tree[point*2+1]);
h[point]=min(h[point*2], h[point*2+1]);
return ret;
}
}seg;
int n, q;
pii range[200010];
pii query[200010];
LL ans[200010], h[200010];
vector<pii> qu[200010], upd[200010];
void solve(){
for(int i=1; i<=n; i++){
qu[i].clear();
upd[i].clear();
}
seg.init();
for(int i=1; i<=n; i++){
int t1=min(i+range[i].F, n+1);
int t2=min(i+range[i].S, n)+1;
upd[t1].pb(mp(i, 1));
upd[t2].pb(mp(i, 0));
}
for(int i=1; i<=q; i++)qu[query[i].S].pb(mp(query[i].F, i));
for(int i=1; i<=n; i++){
for(auto j:upd[i]){
if(j.S)seg.update(1, 1, n, j.F, h[j.F]);
else seg.update(1, 1, n, j.F, llinf);
}
if(i-range[i].F>=1){
seg.alter(1, 1, n, max(1, i-range[i].S), i-range[i].F, h[i]);
}
for(auto j:qu[i]){
//printf("query %d : %lld\n", j.S, seg.query(1, 1, n, j.F, i));
ans[j.S]=max(ans[j.S], seg.query(1, 1, n, j.F, i));
}
}
}
int main(){
scanf("%d", &n);
for(int i=1; i<=n; i++){
scanf("%lld %d %d", &h[i], &range[i].F, &range[i].S);
ans[i]=-1;
}
scanf("%d", &q);
for(int i=1; i<=q; i++)scanf("%d %d", &query[i].F, &query[i].S);
solve();
for(int i=1; i<=n; i++)h[i]=1000000000-h[i];
solve();
for(int i=1; i<=q; i++)printf("%lld\n", ans[i]);
}
Compilation message
antennas.cpp: In function 'int main()':
antennas.cpp:107:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
antennas.cpp:109:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %d %d", &h[i], &range[i].F, &range[i].S);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:112:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
~~~~~^~~~~~~~~~
antennas.cpp:113:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=1; i<=q; i++)scanf("%d %d", &query[i].F, &query[i].S);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
28536 KB |
Output is correct |
| 2 |
Correct |
24 ms |
28536 KB |
Output is correct |
| 3 |
Incorrect |
22 ms |
28540 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
28536 KB |
Output is correct |
| 2 |
Correct |
24 ms |
28536 KB |
Output is correct |
| 3 |
Incorrect |
22 ms |
28540 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
420 ms |
39652 KB |
Output is correct |
| 2 |
Correct |
477 ms |
40420 KB |
Output is correct |
| 3 |
Correct |
347 ms |
38216 KB |
Output is correct |
| 4 |
Correct |
482 ms |
40420 KB |
Output is correct |
| 5 |
Correct |
184 ms |
34152 KB |
Output is correct |
| 6 |
Correct |
453 ms |
40420 KB |
Output is correct |
| 7 |
Correct |
375 ms |
39524 KB |
Output is correct |
| 8 |
Correct |
477 ms |
40464 KB |
Output is correct |
| 9 |
Correct |
64 ms |
30836 KB |
Output is correct |
| 10 |
Correct |
441 ms |
40420 KB |
Output is correct |
| 11 |
Correct |
256 ms |
37604 KB |
Output is correct |
| 12 |
Correct |
447 ms |
40420 KB |
Output is correct |
| 13 |
Correct |
276 ms |
39516 KB |
Output is correct |
| 14 |
Correct |
261 ms |
39084 KB |
Output is correct |
| 15 |
Correct |
267 ms |
39236 KB |
Output is correct |
| 16 |
Correct |
227 ms |
39784 KB |
Output is correct |
| 17 |
Correct |
287 ms |
39844 KB |
Output is correct |
| 18 |
Correct |
263 ms |
39740 KB |
Output is correct |
| 19 |
Correct |
279 ms |
39300 KB |
Output is correct |
| 20 |
Correct |
262 ms |
39164 KB |
Output is correct |
| 21 |
Correct |
254 ms |
38620 KB |
Output is correct |
| 22 |
Correct |
268 ms |
39008 KB |
Output is correct |
| 23 |
Correct |
272 ms |
39404 KB |
Output is correct |
| 24 |
Correct |
230 ms |
39348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
28536 KB |
Output is correct |
| 2 |
Correct |
24 ms |
28536 KB |
Output is correct |
| 3 |
Incorrect |
22 ms |
28540 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
