#include <bits/stdc++.h>
using namespace std;
template<class T, class U>
void ckmin(T &a, U b)
{
if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
if (a < b) a = b;
}
#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
typedef pair<pll, ll> ppl;
const int MAXN = 200013;
const int INF = 1000000007;
const ll LLINF = 2696969696969696969ll;
int N, Q;
pair<ll, pii> arr[MAXN];
pii queries[MAXN];
vi born[MAXN], dead[MAXN];
ll ans[MAXN];
vpi quer[MAXN];
ppl seg[3 * MAXN];
void push(int w, int L, int R)
{
if (L != R)
{
ckmax(seg[w << 1].fi.se, seg[w].fi.se);
ckmax(seg[w << 1 | 1].fi.se, seg[w].fi.se);
}
ckmax(seg[w].se, seg[w].fi.fi + seg[w].fi.se);
seg[w].fi.se = -LLINF;
return;
}
void build(int w, int L, int R)
{
seg[w] = {{-LLINF, -LLINF}, -2 * LLINF};
if (L == R)
{
return;
}
int mid = (L + R) >> 1;
build(w << 1, L, mid);
build(w << 1 | 1, mid + 1, R);
}
void update(int w, int L, int R, int a, ll v)
{
push(w, L, R);
if (a < L || R < a) return;
if (L == R)
{
seg[w].fi.fi = v;
seg[w].fi.se = -LLINF;
// seg[w].se = seg[w].fi.fi + seg[w].fi.se;
return;
}
int mid = (L + R) >> 1;
update(w << 1, L, mid, a, v);
update(w << 1 | 1, mid + 1, R, a, v);
seg[w].fi.fi = max(seg[w << 1].fi.fi, seg[w << 1 | 1].fi.fi);
seg[w].se = max(seg[w << 1].se, seg[w << 1 | 1].se);
return;
}
void rangeupdate(int w, int L, int R, int a, int b, ll v)
{
// if (w == 1) cerr << L << ' ' << R << ' ' << a << ' ' << b << endl;
push(w, L, R);
if (b < L || R < a) return;
if (a <= L && R <= b)
{
ckmax(seg[w].fi.se, v);
push(w, L, R);
// cerr << seg[w].fi.fi << ' ' << seg[w].fi.se << ' ' << seg[w].se << endl;
return;
}
int mid = (L + R) >> 1;
rangeupdate(w << 1, L, mid, a, b, v);
rangeupdate(w << 1 | 1, mid + 1, R, a, b, v);
seg[w].fi.fi = max(seg[w << 1].fi.fi, seg[w << 1 | 1].fi.fi);
seg[w].se = max(seg[w << 1].se, seg[w << 1 | 1].se);
return;
}
ll query(int w, int L, int R, int a, int b)
{
push(w, L, R);
if (a <= L && R <= b)
{
// cerr << seg[w].fi.fi << ' ' << seg[w].fi.se << ' ' << seg[w].se << endl;
return seg[w].se;
}
int mid = (L + R) >> 1;
if (b <= mid) return query(w << 1, L, mid, a, b);
if (mid < a) return query(w << 1 | 1, mid + 1, R, a, b);
return max(query(w << 1, L, mid, a, b), query(w << 1 | 1, mid + 1, R, a, b));
}
void solve()
{
build(1, 0, N - 1);
FOR(i, 0, N)
{
for (int x : born[i])
{
update(1, 0, N - 1, x, -arr[x].fi);
// cerr << "setfi " << x << ' ' << -arr[x].fi << endl;
}
for (int x : dead[i])
{
update(1, 0, N - 1, x, -LLINF);
// cerr << "setfi " << x << ' ' << -LLINF << endl;
}
int lt = max(0, i - arr[i].se.se), rt = i - arr[i].se.fi;
if (lt <= rt)
{
rangeupdate(1, 0, N - 1, lt, rt, arr[i].fi);
// cerr << "setse " << lt << ' ' << rt << ' ' << arr[i].fi << endl;
}
for (pii p : quer[i])
{
auto res = query(1, 0, N - 1, p.fi, i);
// cerr << "ask " << p.fi << " " << i << " " << res << endl;
ckmax(ans[p.se], res);
}
}
}
int32_t main()
{
cout << fixed << setprecision(12);
cerr << fixed << setprecision(4);
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> N;
FOR(i, 0, N)
{
cin >> arr[i].fi >> arr[i].se.fi >> arr[i].se.se;
}
cin >> Q;
FOR(i, 0, Q)
{
cin >> queries[i].fi >> queries[i].se;
queries[i].fi--; queries[i].se--;
quer[queries[i].se].PB({queries[i].fi, i});
ans[i] = -1;
}
FOR(i, 0, N)
{
if (i + arr[i].se.fi < N)
{
born[i + arr[i].se.fi].PB(i);
}
if(i + arr[i].se.se + 1 < N)
{
dead[i + arr[i].se.se + 1].PB(i);
}
}
solve();
FOR(i, 0, N)
{
arr[i].fi = INF - arr[i].fi;
}
solve();
FOR(i, 0, Q)
{
cout << ans[i] << '\n';
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
14456 KB |
Output is correct |
2 |
Correct |
15 ms |
14456 KB |
Output is correct |
3 |
Correct |
15 ms |
14456 KB |
Output is correct |
4 |
Correct |
14 ms |
14456 KB |
Output is correct |
5 |
Correct |
14 ms |
14456 KB |
Output is correct |
6 |
Correct |
16 ms |
14456 KB |
Output is correct |
7 |
Correct |
14 ms |
14584 KB |
Output is correct |
8 |
Correct |
16 ms |
14456 KB |
Output is correct |
9 |
Correct |
15 ms |
14456 KB |
Output is correct |
10 |
Correct |
14 ms |
14456 KB |
Output is correct |
11 |
Correct |
14 ms |
14456 KB |
Output is correct |
12 |
Correct |
15 ms |
14456 KB |
Output is correct |
13 |
Correct |
14 ms |
14456 KB |
Output is correct |
14 |
Correct |
15 ms |
14456 KB |
Output is correct |
15 |
Correct |
15 ms |
14456 KB |
Output is correct |
16 |
Correct |
16 ms |
14456 KB |
Output is correct |
17 |
Correct |
14 ms |
14456 KB |
Output is correct |
18 |
Correct |
16 ms |
14456 KB |
Output is correct |
19 |
Correct |
14 ms |
14456 KB |
Output is correct |
20 |
Correct |
14 ms |
14456 KB |
Output is correct |
21 |
Correct |
15 ms |
14456 KB |
Output is correct |
22 |
Correct |
15 ms |
14712 KB |
Output is correct |
23 |
Correct |
15 ms |
14456 KB |
Output is correct |
24 |
Correct |
14 ms |
14456 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
14456 KB |
Output is correct |
2 |
Correct |
15 ms |
14456 KB |
Output is correct |
3 |
Correct |
15 ms |
14456 KB |
Output is correct |
4 |
Correct |
14 ms |
14456 KB |
Output is correct |
5 |
Correct |
14 ms |
14456 KB |
Output is correct |
6 |
Correct |
16 ms |
14456 KB |
Output is correct |
7 |
Correct |
14 ms |
14584 KB |
Output is correct |
8 |
Correct |
16 ms |
14456 KB |
Output is correct |
9 |
Correct |
15 ms |
14456 KB |
Output is correct |
10 |
Correct |
14 ms |
14456 KB |
Output is correct |
11 |
Correct |
14 ms |
14456 KB |
Output is correct |
12 |
Correct |
15 ms |
14456 KB |
Output is correct |
13 |
Correct |
14 ms |
14456 KB |
Output is correct |
14 |
Correct |
15 ms |
14456 KB |
Output is correct |
15 |
Correct |
15 ms |
14456 KB |
Output is correct |
16 |
Correct |
16 ms |
14456 KB |
Output is correct |
17 |
Correct |
14 ms |
14456 KB |
Output is correct |
18 |
Correct |
16 ms |
14456 KB |
Output is correct |
19 |
Correct |
14 ms |
14456 KB |
Output is correct |
20 |
Correct |
14 ms |
14456 KB |
Output is correct |
21 |
Correct |
15 ms |
14456 KB |
Output is correct |
22 |
Correct |
15 ms |
14712 KB |
Output is correct |
23 |
Correct |
15 ms |
14456 KB |
Output is correct |
24 |
Correct |
14 ms |
14456 KB |
Output is correct |
25 |
Correct |
123 ms |
20984 KB |
Output is correct |
26 |
Correct |
31 ms |
15352 KB |
Output is correct |
27 |
Correct |
177 ms |
23672 KB |
Output is correct |
28 |
Correct |
184 ms |
23672 KB |
Output is correct |
29 |
Correct |
126 ms |
20984 KB |
Output is correct |
30 |
Correct |
128 ms |
20600 KB |
Output is correct |
31 |
Correct |
135 ms |
22648 KB |
Output is correct |
32 |
Correct |
185 ms |
23800 KB |
Output is correct |
33 |
Correct |
163 ms |
23160 KB |
Output is correct |
34 |
Correct |
96 ms |
18936 KB |
Output is correct |
35 |
Correct |
175 ms |
23544 KB |
Output is correct |
36 |
Correct |
176 ms |
23672 KB |
Output is correct |
37 |
Correct |
108 ms |
19320 KB |
Output is correct |
38 |
Correct |
177 ms |
22776 KB |
Output is correct |
39 |
Correct |
38 ms |
15736 KB |
Output is correct |
40 |
Correct |
173 ms |
22776 KB |
Output is correct |
41 |
Correct |
129 ms |
20600 KB |
Output is correct |
42 |
Correct |
172 ms |
22648 KB |
Output is correct |
43 |
Correct |
67 ms |
17272 KB |
Output is correct |
44 |
Correct |
172 ms |
22648 KB |
Output is correct |
45 |
Correct |
43 ms |
15992 KB |
Output is correct |
46 |
Correct |
188 ms |
22776 KB |
Output is correct |
47 |
Correct |
55 ms |
16632 KB |
Output is correct |
48 |
Correct |
173 ms |
22776 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
577 ms |
32888 KB |
Output is correct |
2 |
Correct |
629 ms |
38008 KB |
Output is correct |
3 |
Correct |
403 ms |
34552 KB |
Output is correct |
4 |
Correct |
635 ms |
38112 KB |
Output is correct |
5 |
Correct |
257 ms |
25780 KB |
Output is correct |
6 |
Correct |
636 ms |
37884 KB |
Output is correct |
7 |
Correct |
516 ms |
36472 KB |
Output is correct |
8 |
Correct |
621 ms |
38140 KB |
Output is correct |
9 |
Correct |
83 ms |
17656 KB |
Output is correct |
10 |
Correct |
648 ms |
38136 KB |
Output is correct |
11 |
Correct |
356 ms |
27640 KB |
Output is correct |
12 |
Correct |
632 ms |
38136 KB |
Output is correct |
13 |
Correct |
384 ms |
35444 KB |
Output is correct |
14 |
Correct |
366 ms |
35608 KB |
Output is correct |
15 |
Correct |
359 ms |
35576 KB |
Output is correct |
16 |
Correct |
332 ms |
36216 KB |
Output is correct |
17 |
Correct |
405 ms |
35700 KB |
Output is correct |
18 |
Correct |
373 ms |
36068 KB |
Output is correct |
19 |
Correct |
377 ms |
35408 KB |
Output is correct |
20 |
Correct |
371 ms |
35524 KB |
Output is correct |
21 |
Correct |
348 ms |
35124 KB |
Output is correct |
22 |
Correct |
374 ms |
35572 KB |
Output is correct |
23 |
Correct |
376 ms |
35572 KB |
Output is correct |
24 |
Correct |
316 ms |
35700 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
14456 KB |
Output is correct |
2 |
Correct |
15 ms |
14456 KB |
Output is correct |
3 |
Correct |
15 ms |
14456 KB |
Output is correct |
4 |
Correct |
14 ms |
14456 KB |
Output is correct |
5 |
Correct |
14 ms |
14456 KB |
Output is correct |
6 |
Correct |
16 ms |
14456 KB |
Output is correct |
7 |
Correct |
14 ms |
14584 KB |
Output is correct |
8 |
Correct |
16 ms |
14456 KB |
Output is correct |
9 |
Correct |
15 ms |
14456 KB |
Output is correct |
10 |
Correct |
14 ms |
14456 KB |
Output is correct |
11 |
Correct |
14 ms |
14456 KB |
Output is correct |
12 |
Correct |
15 ms |
14456 KB |
Output is correct |
13 |
Correct |
14 ms |
14456 KB |
Output is correct |
14 |
Correct |
15 ms |
14456 KB |
Output is correct |
15 |
Correct |
15 ms |
14456 KB |
Output is correct |
16 |
Correct |
16 ms |
14456 KB |
Output is correct |
17 |
Correct |
14 ms |
14456 KB |
Output is correct |
18 |
Correct |
16 ms |
14456 KB |
Output is correct |
19 |
Correct |
14 ms |
14456 KB |
Output is correct |
20 |
Correct |
14 ms |
14456 KB |
Output is correct |
21 |
Correct |
15 ms |
14456 KB |
Output is correct |
22 |
Correct |
15 ms |
14712 KB |
Output is correct |
23 |
Correct |
15 ms |
14456 KB |
Output is correct |
24 |
Correct |
14 ms |
14456 KB |
Output is correct |
25 |
Correct |
123 ms |
20984 KB |
Output is correct |
26 |
Correct |
31 ms |
15352 KB |
Output is correct |
27 |
Correct |
177 ms |
23672 KB |
Output is correct |
28 |
Correct |
184 ms |
23672 KB |
Output is correct |
29 |
Correct |
126 ms |
20984 KB |
Output is correct |
30 |
Correct |
128 ms |
20600 KB |
Output is correct |
31 |
Correct |
135 ms |
22648 KB |
Output is correct |
32 |
Correct |
185 ms |
23800 KB |
Output is correct |
33 |
Correct |
163 ms |
23160 KB |
Output is correct |
34 |
Correct |
96 ms |
18936 KB |
Output is correct |
35 |
Correct |
175 ms |
23544 KB |
Output is correct |
36 |
Correct |
176 ms |
23672 KB |
Output is correct |
37 |
Correct |
108 ms |
19320 KB |
Output is correct |
38 |
Correct |
177 ms |
22776 KB |
Output is correct |
39 |
Correct |
38 ms |
15736 KB |
Output is correct |
40 |
Correct |
173 ms |
22776 KB |
Output is correct |
41 |
Correct |
129 ms |
20600 KB |
Output is correct |
42 |
Correct |
172 ms |
22648 KB |
Output is correct |
43 |
Correct |
67 ms |
17272 KB |
Output is correct |
44 |
Correct |
172 ms |
22648 KB |
Output is correct |
45 |
Correct |
43 ms |
15992 KB |
Output is correct |
46 |
Correct |
188 ms |
22776 KB |
Output is correct |
47 |
Correct |
55 ms |
16632 KB |
Output is correct |
48 |
Correct |
173 ms |
22776 KB |
Output is correct |
49 |
Correct |
577 ms |
32888 KB |
Output is correct |
50 |
Correct |
629 ms |
38008 KB |
Output is correct |
51 |
Correct |
403 ms |
34552 KB |
Output is correct |
52 |
Correct |
635 ms |
38112 KB |
Output is correct |
53 |
Correct |
257 ms |
25780 KB |
Output is correct |
54 |
Correct |
636 ms |
37884 KB |
Output is correct |
55 |
Correct |
516 ms |
36472 KB |
Output is correct |
56 |
Correct |
621 ms |
38140 KB |
Output is correct |
57 |
Correct |
83 ms |
17656 KB |
Output is correct |
58 |
Correct |
648 ms |
38136 KB |
Output is correct |
59 |
Correct |
356 ms |
27640 KB |
Output is correct |
60 |
Correct |
632 ms |
38136 KB |
Output is correct |
61 |
Correct |
384 ms |
35444 KB |
Output is correct |
62 |
Correct |
366 ms |
35608 KB |
Output is correct |
63 |
Correct |
359 ms |
35576 KB |
Output is correct |
64 |
Correct |
332 ms |
36216 KB |
Output is correct |
65 |
Correct |
405 ms |
35700 KB |
Output is correct |
66 |
Correct |
373 ms |
36068 KB |
Output is correct |
67 |
Correct |
377 ms |
35408 KB |
Output is correct |
68 |
Correct |
371 ms |
35524 KB |
Output is correct |
69 |
Correct |
348 ms |
35124 KB |
Output is correct |
70 |
Correct |
374 ms |
35572 KB |
Output is correct |
71 |
Correct |
376 ms |
35572 KB |
Output is correct |
72 |
Correct |
316 ms |
35700 KB |
Output is correct |
73 |
Correct |
928 ms |
45492 KB |
Output is correct |
74 |
Correct |
681 ms |
38904 KB |
Output is correct |
75 |
Correct |
848 ms |
45604 KB |
Output is correct |
76 |
Correct |
1087 ms |
49528 KB |
Output is correct |
77 |
Correct |
534 ms |
33528 KB |
Output is correct |
78 |
Correct |
968 ms |
45944 KB |
Output is correct |
79 |
Correct |
1020 ms |
47736 KB |
Output is correct |
80 |
Correct |
1186 ms |
49452 KB |
Output is correct |
81 |
Correct |
375 ms |
27268 KB |
Output is correct |
82 |
Correct |
862 ms |
43964 KB |
Output is correct |
83 |
Correct |
810 ms |
38524 KB |
Output is correct |
84 |
Correct |
1096 ms |
49400 KB |
Output is correct |
85 |
Correct |
624 ms |
41840 KB |
Output is correct |
86 |
Correct |
743 ms |
45812 KB |
Output is correct |
87 |
Correct |
414 ms |
37240 KB |
Output is correct |
88 |
Correct |
804 ms |
46328 KB |
Output is correct |
89 |
Correct |
671 ms |
43460 KB |
Output is correct |
90 |
Correct |
747 ms |
46328 KB |
Output is correct |
91 |
Correct |
547 ms |
39248 KB |
Output is correct |
92 |
Correct |
743 ms |
45632 KB |
Output is correct |
93 |
Correct |
446 ms |
37172 KB |
Output is correct |
94 |
Correct |
746 ms |
45752 KB |
Output is correct |
95 |
Correct |
483 ms |
38388 KB |
Output is correct |
96 |
Correct |
702 ms |
46072 KB |
Output is correct |