#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;
const int maxn = 2e5+5;
int n, q;
int H[maxn], A[maxn], B[maxn];
int ql[maxn], qr[maxn];
int res[maxn];
vector<int> buck[maxn];
vector<int> que[maxn];
int tmp[maxn];
struct segtree
{
struct node
{
int a = -1, b = 1e9;
int res = -1;
};
node st[4*maxn];
void clear()
{
for(int i = 1; i<= 4*n; i++) st[i] = node();
}
void build(int *arr, int p = 1, int L = 1, int R = n)
{
if(L == R)
{
st[p].a = arr[L];
return;
}
int M = (L+R)/2;
build(arr, 2*p, L, M);
build(arr, 2*p+1, M+1, R);
}
void modb(int p, int x)
{
st[p].b = min(st[p].b, x);
st[p].res = max(st[p].res, st[p].a-st[p].b);
}
void push(int p)
{
modb(2*p, st[p].b);
modb(2*p+1, st[p].b);
st[p].b = 1e9;
}
void update(int p)
{
st[p].a = max(st[2*p].a, st[2*p+1].a);
st[p].res = max(max(st[p].res, st[2*p].res), max(st[2*p+1].res, st[p].a-st[p].b));
}
void rngb(int i, int j, int dx, int p = 1, int L = 1, int R = n)
{
if(i> R || j< L) return;
if(i<= L && R<= j)
{
modb(p, dx);
return;
}
push(p);
int M = (L+R)/2;
rngb(i, j, dx, 2*p, L, M);
rngb(i, j, dx, 2*p+1, M+1, R);
update(p);
}
void pointa(int x, int dx, int p = 1, int L = 1, int R = n)
{
if(L == R)
{
st[p].a += dx;
st[p].b = 1e9;
return;
}
push(p);
int M = (L+R)/2;
if(x<= M) pointa(x, dx, 2*p, L, M);
else pointa(x, dx, 2*p+1, M+1, R);
update(p);
}
int ask(int i, int j, int p = 1, int L = 1, int R = n)
{
if(i> R || j< L) return -1;
if(i<= L && R<= j) return st[p].res;
push(p);
int M = (L+R)/2;
int x = ask(i, j, 2*p, L, M);
int y = ask(i, j, 2*p+1, M+1, R);
return max(x, y);
}
};
segtree foo;
void solve()
{
foo.clear();
for(int i = 1; i<= n; i++) buck[i].clear();
for(int i = 1; i<= n; i++) que[i].clear();
for(int i = 1; i<= n; i++)
{
buck[max(0, i-A[i])].pb(i);
buck[max(0, i-B[i]-1)].pb(-i);
}
for(int i = 1; i<= q; i++)
{
que[ql[i]].pb(i);
}
for(int i = 1; i<= n; i++) tmp[i] = H[i]-1e9;
foo.build(tmp);
for(int i = n; i>= 1; i--)
{
for(int x : buck[i])
{
if(x> 0) foo.pointa(x, 1e9);
else foo.pointa(-x, -1e9);
}
foo.rngb(min(i+A[i], n), min(i+B[i], n), H[i]);
for(int k : que[i])
{
res[k] = max(res[k], foo.ask(ql[k], qr[k]));
}
}
}
int main()
{
scanf("%d", &n);
for(int i = 1; i<= n; i++)
{
scanf("%d %d %d", &H[i], &A[i], &B[i]);
}
scanf("%d", &q);
for(int i = 1; i<= q; i++)
{
scanf("%d %d", &ql[i], &qr[i]);
}
memset(res, -1, sizeof res);
solve();
reverse(H+1, H+n+1);
reverse(A+1, A+n+1);
reverse(B+1, B+n+1);
for(int i = 1; i<= q; i++)
{
int l = ql[i], r = qr[i];
ql[i] = n+1-r;
qr[i] = n+1-l;
}
solve();
for(int i = 1; i<= q; i++) printf("%d\n", res[i]);
}
Compilation message
antennas.cpp: In function 'int main()':
antennas.cpp:139:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
antennas.cpp:142:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &H[i], &A[i], &B[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:144:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
~~~~~^~~~~~~~~~
antennas.cpp:147:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &ql[i], &qr[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
11 ms |
10616 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
11 ms |
10616 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
390 ms |
27236 KB |
Output is correct |
2 |
Correct |
438 ms |
29064 KB |
Output is correct |
3 |
Correct |
291 ms |
23616 KB |
Output is correct |
4 |
Correct |
419 ms |
29156 KB |
Output is correct |
5 |
Correct |
184 ms |
19092 KB |
Output is correct |
6 |
Correct |
427 ms |
29256 KB |
Output is correct |
7 |
Correct |
362 ms |
26608 KB |
Output is correct |
8 |
Correct |
425 ms |
29088 KB |
Output is correct |
9 |
Correct |
61 ms |
13576 KB |
Output is correct |
10 |
Correct |
435 ms |
29148 KB |
Output is correct |
11 |
Correct |
257 ms |
22412 KB |
Output is correct |
12 |
Correct |
434 ms |
29012 KB |
Output is correct |
13 |
Correct |
302 ms |
27844 KB |
Output is correct |
14 |
Correct |
293 ms |
27592 KB |
Output is correct |
15 |
Correct |
291 ms |
26780 KB |
Output is correct |
16 |
Correct |
270 ms |
26956 KB |
Output is correct |
17 |
Correct |
303 ms |
28188 KB |
Output is correct |
18 |
Correct |
292 ms |
27164 KB |
Output is correct |
19 |
Correct |
296 ms |
27276 KB |
Output is correct |
20 |
Correct |
292 ms |
27684 KB |
Output is correct |
21 |
Correct |
288 ms |
27968 KB |
Output is correct |
22 |
Correct |
285 ms |
27560 KB |
Output is correct |
23 |
Correct |
293 ms |
27376 KB |
Output is correct |
24 |
Correct |
272 ms |
26616 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
11 ms |
10616 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |