#include <bits/stdc++.h>
using namespace std;
const int DIM = 200005;
const int INF = 1000000007;
int sgt1[DIM << 2], sgt2[DIM << 2], lzy[DIM << 2], ans[DIM];
vector<int> upd[DIM], lst[DIM];
struct Antenna {
int h, a, b; } arr[DIM];
struct Query {
int l, r; } qry[DIM];
void updateLazy(int nd, int le, int ri) {
sgt2[nd] = max(sgt2[nd], lzy[nd] - sgt1[nd]);
if (le != ri) {
lzy[nd << 1] = max(lzy[nd << 1], lzy[nd]);
lzy[nd << 1 | 1] = max(lzy[nd << 1 | 1], lzy[nd]); }
lzy[nd] = 0; }
void build(int nd, int le, int ri) {
sgt1[nd] = INF; sgt2[nd] = -1; lzy[nd] = 0;
if (le != ri) {
int md = (le + ri) >> 1;
build(nd << 1, le, md);
build(nd << 1 | 1, md + 1, ri); } }
void update1(int nd, int le, int ri, int ps, int vl) {
if (le == ri) {
sgt1[nd] = vl; }
else {
int md = (le + ri) >> 1;
if (ps <= md) {
update1(nd << 1, le, md, ps, vl); }
else {
update1(nd << 1 | 1, md + 1, ri, ps, vl); }
sgt1[nd] = min(sgt1[nd << 1], sgt1[nd << 1 | 1]); } }
void update2(int nd, int le, int ri, int st, int en, int vl) {
updateLazy(nd, le, ri);
if (st <= le and ri <= en) {
lzy[nd] = max(lzy[nd], vl);
updateLazy(nd, le, ri); }
else {
int md = (le + ri) >> 1;
if (st <= md) {
update2(nd << 1, le, md, st, en, vl); }
if (md < en) {
update2(nd << 1 | 1, md + 1, ri, st, en, vl); }
sgt2[nd] = max(sgt2[nd << 1], sgt2[nd << 1 | 1]); } }
int query(int nd, int le, int ri, int st, int en) {
updateLazy(nd, le, ri);
if (st <= le and ri <= en) {
return sgt2[nd]; }
else {
int md = (le + ri) >> 1;
if (en <= md) {
return query(nd << 1, le, md, st, en); }
else if (md < st) {
return query(nd << 1 | 1, md + 1, ri, st, en); }
else {
return max(query(nd << 1, le, md, st, en),
query(nd << 1 | 1, md + 1, ri, st, en)); } } }
int main(void) {
#ifdef HOME
freopen("antennas.in", "r", stdin);
freopen("antennas.out", "w", stdout);
#endif
int N; cin >> N;
for (int i = 1; i <= N; ++i) {
cin >> arr[i].h >> arr[i].a >> arr[i].b; }
int Q; cin >> Q;
for (int i = 1; i <= Q; ++i) {
cin >> qry[i].l >> qry[i].r; ans[i] = -1; }
for (int g = 1; g <= 2; ++g) {
for (int i = 1; i <= N; ++i) {
if (i + arr[i].a <= N) {
upd[i + arr[i].a].push_back(i); }
if (i + arr[i].b < N) {
upd[i + arr[i].b + 1].push_back(-i); } }
for (int i = 1; i <= Q; ++i) {
lst[qry[i].r].push_back(i); }
build(1, 1, N);
for (int i = 1; i <= N; ++i) {
for (int x : upd[i]) {
query(1, 1, N, abs(x), abs(x));
if (x > 0) {
update1(1, 1, N, x, arr[x].h); }
else {
update1(1, 1, N, -x, INF); } }
if (i - arr[i].a >= 1) {
update2(1, 1, N, max(1, i - arr[i].b), i - arr[i].a, arr[i].h); }
for (int x : lst[i]) {
ans[x] = max(ans[x], query(1, 1, N, qry[x].l, qry[x].r)); } }
for (int i = 1; i <= N; ++i) {
upd[i].clear(); lst[i].clear(); }
for (int i = 1, j = N; i <= j; ++i, --j) {
swap(arr[i], arr[j]); }
for (int i = 1; i <= Q; ++i) {
qry[i] = {N - qry[i].r + 1, N - qry[i].l + 1}; } }
for (int i = 1; i <= Q; ++i) {
cout << ans[i] << "\n"; }
return 0; }
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
9728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
9728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
481 ms |
21820 KB |
Output is correct |
| 2 |
Correct |
560 ms |
22436 KB |
Output is correct |
| 3 |
Correct |
367 ms |
20412 KB |
Output is correct |
| 4 |
Correct |
545 ms |
22392 KB |
Output is correct |
| 5 |
Correct |
224 ms |
15864 KB |
Output is correct |
| 6 |
Correct |
535 ms |
22420 KB |
Output is correct |
| 7 |
Correct |
465 ms |
21752 KB |
Output is correct |
| 8 |
Correct |
547 ms |
22520 KB |
Output is correct |
| 9 |
Correct |
72 ms |
11512 KB |
Output is correct |
| 10 |
Correct |
525 ms |
22392 KB |
Output is correct |
| 11 |
Incorrect |
315 ms |
17000 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
9728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
