#include <bits/stdc++.h>
#define yes { cout << "YES" << endl; exit(0); }
#define no { cout << "NO" << endl; exit(0); }
#define impossible { cout << "Impossible" << endl; exit(0); }
using namespace std;
typedef long long ll;
typedef pair<int,int> Pair;
const int inf = 1e9;
const int Nmax = 4e5 + 5;
int L[Nmax], R[Nmax], ans[Nmax], H[Nmax], A[Nmax], B[Nmax];
int n, q;
vector<int> when[Nmax], add[Nmax], er[Nmax];
#define left_son (node<<1)
#define right_son ((node<<1)|1)
#define mid ((st+dr)>>1)
class SegTree
{
int val[Nmax<<2], best[Nmax<<2], lazy[Nmax<<2];
void propag(int node)
{
if(lazy[node] == inf) return;
lazy[left_son] = min(lazy[left_son], lazy[node]);
best[left_son] = max(best[left_son], val[left_son] - lazy[left_son]);
lazy[right_son] = min(lazy[right_son], lazy[node]);
best[right_son] = max(best[right_son], val[right_son] - lazy[right_son]);
lazy[node] = inf;
}
public:
void init(int node, int st, int dr)
{
best[node] = -inf;
val[node] = -inf;
lazy[node] = inf;
if(st == dr) return;
init(left_son, st, mid);
init(right_son, mid+1, dr);
}
void upd1(int node, int st, int dr, int pos, int mxVal)
{
if(st == dr)
{
val[node] = mxVal;
// best[node] = max(best[node], val[node] - lazy[node]);
lazy[node] = inf;
return;
}
propag(node);
if(pos <= mid) upd1(left_son, st, mid, pos, mxVal);
else upd1(right_son, mid+1, dr, pos, mxVal);
val[node] = max(val[left_son], val[right_son]);
best[node] = max(best[left_son], best[right_son]);
}
void upd2(int node, int st, int dr, int L, int R, int mnVal)
{
if(L <= st && dr <= R)
{
lazy[node] = min(lazy[node], mnVal);
best[node] = max(best[node], val[node] - lazy[node]);
return;
}
propag(node);
if(L <= mid) upd2(left_son, st, mid, L, R, mnVal);
if(mid < R) upd2(right_son, mid+1, dr, L, R, mnVal);
// val[node] = max(val[left_son], val[right_son]);
best[node] = max(best[left_son], best[right_son]);
}
int query(int node, int st, int dr, int L, int R)
{
if(L > dr || R < st) return -inf;
if(L <= st && dr <= R) return best[node];
propag(node);
return max( query(left_son, st, mid, L, R), query(right_son, mid+1, dr, L, R) );
}
} aint;
void solve()
{
aint.init(1, 1, n);
int i;
for(i=1; i<=n; ++i)
{
add[i+A[i]].push_back(i);
er[i+B[i]].push_back(i);
}
for(i=1; i<=q; ++i)
when[R[i]].push_back(i);
for(i=1; i<=n; ++i)
{
for(auto it : add[i])
aint.upd1(1, 1, n, it, H[it]);
int l, r;
l = max(1, i - B[i]);
r = i - A[i];
if(l <= r)
aint.upd2(1, 1, n, l, r, H[i]);
for(auto it : when[i])
ans[it] = max(ans[it], aint.query(1, 1, n, L[it], i));
for(auto it : er[i])
aint.upd1(1, 1, n, it, -inf);
}
}
void clr()
{
int i;
for(i=1; i<=n; ++i)
{
when[i].clear();
add[i].clear();
er[i].clear();
}
}
int main()
{
cin.sync_with_stdio(false); cin.tie(0);
int i;
cin >> n;
for(i=1; i<=n; ++i) cin >> H[i] >> A[i] >> B[i];
cin >> q;
for(i=1; i<=q; ++i)
{
ans[i] = -1;
cin >> L[i] >> R[i];
}
solve();
clr();
for(i=1; i<=q; ++i)
{
L[i] = n+1-L[i];
R[i] = n+1-R[i];
swap(L[i], R[i]);
}
reverse(H+1, H+n+1);
reverse(A+1, A+n+1);
reverse(B+1, B+n+1);
solve();
for(i=1; i<=q; ++i) cout << ans[i] << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
28544 KB |
Output is correct |
2 |
Correct |
22 ms |
28672 KB |
Output is correct |
3 |
Correct |
22 ms |
28672 KB |
Output is correct |
4 |
Correct |
22 ms |
28672 KB |
Output is correct |
5 |
Correct |
22 ms |
28672 KB |
Output is correct |
6 |
Correct |
22 ms |
28672 KB |
Output is correct |
7 |
Correct |
22 ms |
28664 KB |
Output is correct |
8 |
Correct |
22 ms |
28672 KB |
Output is correct |
9 |
Correct |
21 ms |
28544 KB |
Output is correct |
10 |
Correct |
21 ms |
28672 KB |
Output is correct |
11 |
Correct |
22 ms |
28672 KB |
Output is correct |
12 |
Correct |
22 ms |
28672 KB |
Output is correct |
13 |
Correct |
21 ms |
28544 KB |
Output is correct |
14 |
Correct |
22 ms |
28672 KB |
Output is correct |
15 |
Correct |
21 ms |
28672 KB |
Output is correct |
16 |
Correct |
21 ms |
28544 KB |
Output is correct |
17 |
Correct |
26 ms |
28672 KB |
Output is correct |
18 |
Correct |
23 ms |
28672 KB |
Output is correct |
19 |
Correct |
22 ms |
28544 KB |
Output is correct |
20 |
Correct |
21 ms |
28544 KB |
Output is correct |
21 |
Correct |
21 ms |
28672 KB |
Output is correct |
22 |
Correct |
21 ms |
28672 KB |
Output is correct |
23 |
Correct |
21 ms |
28672 KB |
Output is correct |
24 |
Correct |
22 ms |
28664 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
28544 KB |
Output is correct |
2 |
Correct |
22 ms |
28672 KB |
Output is correct |
3 |
Correct |
22 ms |
28672 KB |
Output is correct |
4 |
Correct |
22 ms |
28672 KB |
Output is correct |
5 |
Correct |
22 ms |
28672 KB |
Output is correct |
6 |
Correct |
22 ms |
28672 KB |
Output is correct |
7 |
Correct |
22 ms |
28664 KB |
Output is correct |
8 |
Correct |
22 ms |
28672 KB |
Output is correct |
9 |
Correct |
21 ms |
28544 KB |
Output is correct |
10 |
Correct |
21 ms |
28672 KB |
Output is correct |
11 |
Correct |
22 ms |
28672 KB |
Output is correct |
12 |
Correct |
22 ms |
28672 KB |
Output is correct |
13 |
Correct |
21 ms |
28544 KB |
Output is correct |
14 |
Correct |
22 ms |
28672 KB |
Output is correct |
15 |
Correct |
21 ms |
28672 KB |
Output is correct |
16 |
Correct |
21 ms |
28544 KB |
Output is correct |
17 |
Correct |
26 ms |
28672 KB |
Output is correct |
18 |
Correct |
23 ms |
28672 KB |
Output is correct |
19 |
Correct |
22 ms |
28544 KB |
Output is correct |
20 |
Correct |
21 ms |
28544 KB |
Output is correct |
21 |
Correct |
21 ms |
28672 KB |
Output is correct |
22 |
Correct |
21 ms |
28672 KB |
Output is correct |
23 |
Correct |
21 ms |
28672 KB |
Output is correct |
24 |
Correct |
22 ms |
28664 KB |
Output is correct |
25 |
Correct |
109 ms |
34040 KB |
Output is correct |
26 |
Correct |
35 ms |
29432 KB |
Output is correct |
27 |
Correct |
152 ms |
36344 KB |
Output is correct |
28 |
Correct |
155 ms |
36344 KB |
Output is correct |
29 |
Correct |
117 ms |
34168 KB |
Output is correct |
30 |
Correct |
113 ms |
33912 KB |
Output is correct |
31 |
Correct |
120 ms |
35452 KB |
Output is correct |
32 |
Correct |
155 ms |
36344 KB |
Output is correct |
33 |
Correct |
145 ms |
35960 KB |
Output is correct |
34 |
Correct |
88 ms |
32376 KB |
Output is correct |
35 |
Correct |
154 ms |
36584 KB |
Output is correct |
36 |
Correct |
159 ms |
36344 KB |
Output is correct |
37 |
Correct |
100 ms |
32632 KB |
Output is correct |
38 |
Correct |
164 ms |
35272 KB |
Output is correct |
39 |
Correct |
42 ms |
29688 KB |
Output is correct |
40 |
Correct |
150 ms |
35320 KB |
Output is correct |
41 |
Correct |
120 ms |
33656 KB |
Output is correct |
42 |
Correct |
156 ms |
35340 KB |
Output is correct |
43 |
Correct |
65 ms |
30968 KB |
Output is correct |
44 |
Correct |
157 ms |
35296 KB |
Output is correct |
45 |
Correct |
45 ms |
29944 KB |
Output is correct |
46 |
Correct |
152 ms |
35452 KB |
Output is correct |
47 |
Correct |
57 ms |
30456 KB |
Output is correct |
48 |
Correct |
152 ms |
35324 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
417 ms |
50300 KB |
Output is correct |
2 |
Correct |
462 ms |
51940 KB |
Output is correct |
3 |
Correct |
313 ms |
47096 KB |
Output is correct |
4 |
Correct |
457 ms |
51832 KB |
Output is correct |
5 |
Correct |
192 ms |
40184 KB |
Output is correct |
6 |
Correct |
470 ms |
51832 KB |
Output is correct |
7 |
Correct |
400 ms |
49916 KB |
Output is correct |
8 |
Correct |
468 ms |
51808 KB |
Output is correct |
9 |
Correct |
67 ms |
32632 KB |
Output is correct |
10 |
Correct |
479 ms |
51832 KB |
Output is correct |
11 |
Correct |
257 ms |
42744 KB |
Output is correct |
12 |
Correct |
473 ms |
51932 KB |
Output is correct |
13 |
Correct |
246 ms |
47224 KB |
Output is correct |
14 |
Correct |
240 ms |
46884 KB |
Output is correct |
15 |
Correct |
229 ms |
46512 KB |
Output is correct |
16 |
Correct |
220 ms |
47216 KB |
Output is correct |
17 |
Correct |
248 ms |
47616 KB |
Output is correct |
18 |
Correct |
229 ms |
46456 KB |
Output is correct |
19 |
Correct |
237 ms |
46672 KB |
Output is correct |
20 |
Correct |
263 ms |
46912 KB |
Output is correct |
21 |
Correct |
234 ms |
47832 KB |
Output is correct |
22 |
Correct |
231 ms |
46964 KB |
Output is correct |
23 |
Correct |
245 ms |
46836 KB |
Output is correct |
24 |
Correct |
218 ms |
46456 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
28544 KB |
Output is correct |
2 |
Correct |
22 ms |
28672 KB |
Output is correct |
3 |
Correct |
22 ms |
28672 KB |
Output is correct |
4 |
Correct |
22 ms |
28672 KB |
Output is correct |
5 |
Correct |
22 ms |
28672 KB |
Output is correct |
6 |
Correct |
22 ms |
28672 KB |
Output is correct |
7 |
Correct |
22 ms |
28664 KB |
Output is correct |
8 |
Correct |
22 ms |
28672 KB |
Output is correct |
9 |
Correct |
21 ms |
28544 KB |
Output is correct |
10 |
Correct |
21 ms |
28672 KB |
Output is correct |
11 |
Correct |
22 ms |
28672 KB |
Output is correct |
12 |
Correct |
22 ms |
28672 KB |
Output is correct |
13 |
Correct |
21 ms |
28544 KB |
Output is correct |
14 |
Correct |
22 ms |
28672 KB |
Output is correct |
15 |
Correct |
21 ms |
28672 KB |
Output is correct |
16 |
Correct |
21 ms |
28544 KB |
Output is correct |
17 |
Correct |
26 ms |
28672 KB |
Output is correct |
18 |
Correct |
23 ms |
28672 KB |
Output is correct |
19 |
Correct |
22 ms |
28544 KB |
Output is correct |
20 |
Correct |
21 ms |
28544 KB |
Output is correct |
21 |
Correct |
21 ms |
28672 KB |
Output is correct |
22 |
Correct |
21 ms |
28672 KB |
Output is correct |
23 |
Correct |
21 ms |
28672 KB |
Output is correct |
24 |
Correct |
22 ms |
28664 KB |
Output is correct |
25 |
Correct |
109 ms |
34040 KB |
Output is correct |
26 |
Correct |
35 ms |
29432 KB |
Output is correct |
27 |
Correct |
152 ms |
36344 KB |
Output is correct |
28 |
Correct |
155 ms |
36344 KB |
Output is correct |
29 |
Correct |
117 ms |
34168 KB |
Output is correct |
30 |
Correct |
113 ms |
33912 KB |
Output is correct |
31 |
Correct |
120 ms |
35452 KB |
Output is correct |
32 |
Correct |
155 ms |
36344 KB |
Output is correct |
33 |
Correct |
145 ms |
35960 KB |
Output is correct |
34 |
Correct |
88 ms |
32376 KB |
Output is correct |
35 |
Correct |
154 ms |
36584 KB |
Output is correct |
36 |
Correct |
159 ms |
36344 KB |
Output is correct |
37 |
Correct |
100 ms |
32632 KB |
Output is correct |
38 |
Correct |
164 ms |
35272 KB |
Output is correct |
39 |
Correct |
42 ms |
29688 KB |
Output is correct |
40 |
Correct |
150 ms |
35320 KB |
Output is correct |
41 |
Correct |
120 ms |
33656 KB |
Output is correct |
42 |
Correct |
156 ms |
35340 KB |
Output is correct |
43 |
Correct |
65 ms |
30968 KB |
Output is correct |
44 |
Correct |
157 ms |
35296 KB |
Output is correct |
45 |
Correct |
45 ms |
29944 KB |
Output is correct |
46 |
Correct |
152 ms |
35452 KB |
Output is correct |
47 |
Correct |
57 ms |
30456 KB |
Output is correct |
48 |
Correct |
152 ms |
35324 KB |
Output is correct |
49 |
Correct |
417 ms |
50300 KB |
Output is correct |
50 |
Correct |
462 ms |
51940 KB |
Output is correct |
51 |
Correct |
313 ms |
47096 KB |
Output is correct |
52 |
Correct |
457 ms |
51832 KB |
Output is correct |
53 |
Correct |
192 ms |
40184 KB |
Output is correct |
54 |
Correct |
470 ms |
51832 KB |
Output is correct |
55 |
Correct |
400 ms |
49916 KB |
Output is correct |
56 |
Correct |
468 ms |
51808 KB |
Output is correct |
57 |
Correct |
67 ms |
32632 KB |
Output is correct |
58 |
Correct |
479 ms |
51832 KB |
Output is correct |
59 |
Correct |
257 ms |
42744 KB |
Output is correct |
60 |
Correct |
473 ms |
51932 KB |
Output is correct |
61 |
Correct |
246 ms |
47224 KB |
Output is correct |
62 |
Correct |
240 ms |
46884 KB |
Output is correct |
63 |
Correct |
229 ms |
46512 KB |
Output is correct |
64 |
Correct |
220 ms |
47216 KB |
Output is correct |
65 |
Correct |
248 ms |
47616 KB |
Output is correct |
66 |
Correct |
229 ms |
46456 KB |
Output is correct |
67 |
Correct |
237 ms |
46672 KB |
Output is correct |
68 |
Correct |
263 ms |
46912 KB |
Output is correct |
69 |
Correct |
234 ms |
47832 KB |
Output is correct |
70 |
Correct |
231 ms |
46964 KB |
Output is correct |
71 |
Correct |
245 ms |
46836 KB |
Output is correct |
72 |
Correct |
218 ms |
46456 KB |
Output is correct |
73 |
Correct |
691 ms |
62924 KB |
Output is correct |
74 |
Correct |
492 ms |
56952 KB |
Output is correct |
75 |
Correct |
611 ms |
60336 KB |
Output is correct |
76 |
Correct |
823 ms |
67704 KB |
Output is correct |
77 |
Correct |
393 ms |
49016 KB |
Output is correct |
78 |
Correct |
701 ms |
64504 KB |
Output is correct |
79 |
Correct |
718 ms |
64376 KB |
Output is correct |
80 |
Correct |
778 ms |
67704 KB |
Output is correct |
81 |
Correct |
275 ms |
41080 KB |
Output is correct |
82 |
Correct |
673 ms |
62648 KB |
Output is correct |
83 |
Correct |
550 ms |
55380 KB |
Output is correct |
84 |
Correct |
805 ms |
67680 KB |
Output is correct |
85 |
Correct |
422 ms |
58144 KB |
Output is correct |
86 |
Correct |
540 ms |
61184 KB |
Output is correct |
87 |
Correct |
273 ms |
52292 KB |
Output is correct |
88 |
Correct |
537 ms |
61808 KB |
Output is correct |
89 |
Correct |
492 ms |
59896 KB |
Output is correct |
90 |
Correct |
554 ms |
61048 KB |
Output is correct |
91 |
Correct |
356 ms |
54992 KB |
Output is correct |
92 |
Correct |
531 ms |
61380 KB |
Output is correct |
93 |
Correct |
295 ms |
54120 KB |
Output is correct |
94 |
Correct |
551 ms |
61556 KB |
Output is correct |
95 |
Correct |
348 ms |
54276 KB |
Output is correct |
96 |
Correct |
525 ms |
61044 KB |
Output is correct |