#include <iostream>
#include <vector>
#include <tuple>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <array>
#include <random>
#include <climits>
#include <cassert>
#include <algorithm>
#include <functional>
using namespace std;
template<typename A, typename B> ostream& operator << (ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator << (ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) { os << sep << x, sep = ", "; } return os << '}'; }
void D_out() { cerr << endl; }
template<typename Head, typename... Tail> void D_out(Head H, Tail... T) { cerr << ' ' << H; D_out(T...); }
#ifdef DEBUG
#define D(...) cerr << '(' << #__VA_ARGS__ << "):", D_out(__VA_ARGS__)
#else
#define D(...)
#endif
#define int long long
#define ll long long
#define ld long double
#define f first
#define s second
#define sz(x) ((int) x.size())
#define all(x) (x).begin(), (x).end()
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
struct Node {
int l, r, c, d, lazy;
Node *lft, *rht;
Node (int tl, int tr): l(tl), r(tr), c(0), d(-1), lazy(1e18) {
if (l + 1 != r) {
lft = new Node(l, (l + r) / 2);
rht = new Node((l + r) / 2, r);
} else {
lft = rht = NULL;
}
}
};
void propagate(Node *x) {
if (x->lazy != 1e18) {
x->d = max(x->d, x->c - x->lazy);
if (x->lft) x->lft->lazy = min(x->lft->lazy, x->lazy);
if (x->rht) x->rht->lazy = min(x->rht->lazy, x->lazy);
x->lazy = 1e18;
}
}
void update1(Node *x, int pos, int v) {
propagate(x);
if (pos < x->l || x->r <= pos) {
return;
}
if (x->l + 1 == x->r) {
x->c = v;
return;
}
update1(x->lft, pos, v);
update1(x->rht, pos, v);
x->c = max(x->lft->c, x->rht->c);
x->d = max(x->lft->d, x->rht->d);
}
void update2(Node *x, int l, int r, int v) {
propagate(x);
if (r <= x->l || x->r <= l) {
return;
}
if (l <= x->l && x->r <= r) {
x->lazy = v;
propagate(x);
return;
}
update2(x->lft, l, r, v);
update2(x->rht, l, r, v);
x->c = max(x->lft->c, x->rht->c);
x->d = max(x->lft->d, x->rht->d);
}
int query(Node *x, int l, int r) {
propagate(x);
if (r <= x->l || x->r <= l) {
return -1e18;
}
if (l <= x->l && x->r <= r) {
return x->d;
}
return max(query(x->lft, l, r), query(x->rht, l, r));
}
int n, q, ans[200005];
vector<array<int, 3>> v;
vector<pair<int, int>> queries, currq[200005];
vector<int> make[200005], kill[200005];
Node *root;
void solve() {
cin >> n;
v.resize(n);
for (int i = 0; i < n; i++) {
cin >> v[i][0] >> v[i][1] >> v[i][2];
}
cin >> q;
for (int i = 0, l, r; i < q; i++) {
cin >> l >> r;
l--;
r--;
queries.push_back({l, r});
}
fill(ans, ans + 200005, -1);
function<void()> sweep = [&] () {
root = new Node(0, 200005);
for (int i = 0; i < 200005; i++) {
currq[i].clear();
make[i].clear();
kill[i].clear();
}
for (int i = 0; i < q; i++) {
currq[queries[i].s].push_back({queries[i].f, i});
}
for (int i = 0; i < n; i++) {
if (i + v[i][1] < n) {
make[i + v[i][1]].push_back(i);
}
if (i + v[i][2] < n) {
kill[i + v[i][2]].push_back(i);
}
for (int j : make[i]) {
update1(root, j, v[j][0]);
}
if (i - v[i][1] >= 0) {
update2(root, max(i - v[i][2], 0ll), i - v[i][1] + 1, v[i][0]);
}
for (pair<int, int> j : currq[i]) {
ans[j.s] = max(ans[j.s], query(root, j.f, i + 1));
}
for (int j : kill[i]) {
update1(root, j, 0);
}
}
};
sweep();
reverse(all(v));
D(queries);
for (pair<int, int> &q : queries) {
int nqf = n - q.s - 1, nqs = n - q.f - 1;
q = {nqf, nqs};
}
D(queries);
sweep();
for (int i = 0; i < q; i++) {
cout << ans[i] << "\n";
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int t = 1; //cin >> t;
for (int tc = 1; tc <= t; tc++) {
//cout << "Case #" << tc << ": ";
solve();
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
38 ms |
66168 KB |
Output is correct |
2 |
Correct |
37 ms |
66140 KB |
Output is correct |
3 |
Correct |
38 ms |
66236 KB |
Output is correct |
4 |
Correct |
37 ms |
66228 KB |
Output is correct |
5 |
Correct |
37 ms |
66128 KB |
Output is correct |
6 |
Correct |
41 ms |
66136 KB |
Output is correct |
7 |
Correct |
36 ms |
66140 KB |
Output is correct |
8 |
Correct |
37 ms |
66128 KB |
Output is correct |
9 |
Correct |
37 ms |
66004 KB |
Output is correct |
10 |
Correct |
38 ms |
66292 KB |
Output is correct |
11 |
Correct |
37 ms |
66136 KB |
Output is correct |
12 |
Correct |
36 ms |
66064 KB |
Output is correct |
13 |
Correct |
36 ms |
66132 KB |
Output is correct |
14 |
Correct |
36 ms |
65996 KB |
Output is correct |
15 |
Correct |
37 ms |
66128 KB |
Output is correct |
16 |
Correct |
45 ms |
66132 KB |
Output is correct |
17 |
Correct |
36 ms |
66132 KB |
Output is correct |
18 |
Correct |
36 ms |
66132 KB |
Output is correct |
19 |
Correct |
36 ms |
66140 KB |
Output is correct |
20 |
Correct |
37 ms |
66120 KB |
Output is correct |
21 |
Correct |
37 ms |
66132 KB |
Output is correct |
22 |
Correct |
37 ms |
66132 KB |
Output is correct |
23 |
Correct |
36 ms |
66220 KB |
Output is correct |
24 |
Correct |
36 ms |
66128 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
38 ms |
66168 KB |
Output is correct |
2 |
Correct |
37 ms |
66140 KB |
Output is correct |
3 |
Correct |
38 ms |
66236 KB |
Output is correct |
4 |
Correct |
37 ms |
66228 KB |
Output is correct |
5 |
Correct |
37 ms |
66128 KB |
Output is correct |
6 |
Correct |
41 ms |
66136 KB |
Output is correct |
7 |
Correct |
36 ms |
66140 KB |
Output is correct |
8 |
Correct |
37 ms |
66128 KB |
Output is correct |
9 |
Correct |
37 ms |
66004 KB |
Output is correct |
10 |
Correct |
38 ms |
66292 KB |
Output is correct |
11 |
Correct |
37 ms |
66136 KB |
Output is correct |
12 |
Correct |
36 ms |
66064 KB |
Output is correct |
13 |
Correct |
36 ms |
66132 KB |
Output is correct |
14 |
Correct |
36 ms |
65996 KB |
Output is correct |
15 |
Correct |
37 ms |
66128 KB |
Output is correct |
16 |
Correct |
45 ms |
66132 KB |
Output is correct |
17 |
Correct |
36 ms |
66132 KB |
Output is correct |
18 |
Correct |
36 ms |
66132 KB |
Output is correct |
19 |
Correct |
36 ms |
66140 KB |
Output is correct |
20 |
Correct |
37 ms |
66120 KB |
Output is correct |
21 |
Correct |
37 ms |
66132 KB |
Output is correct |
22 |
Correct |
37 ms |
66132 KB |
Output is correct |
23 |
Correct |
36 ms |
66220 KB |
Output is correct |
24 |
Correct |
36 ms |
66128 KB |
Output is correct |
25 |
Correct |
147 ms |
77380 KB |
Output is correct |
26 |
Correct |
51 ms |
67276 KB |
Output is correct |
27 |
Correct |
193 ms |
79544 KB |
Output is correct |
28 |
Correct |
196 ms |
79288 KB |
Output is correct |
29 |
Correct |
148 ms |
76964 KB |
Output is correct |
30 |
Correct |
145 ms |
76984 KB |
Output is correct |
31 |
Correct |
176 ms |
78764 KB |
Output is correct |
32 |
Correct |
195 ms |
79192 KB |
Output is correct |
33 |
Correct |
186 ms |
79036 KB |
Output is correct |
34 |
Correct |
116 ms |
72384 KB |
Output is correct |
35 |
Correct |
189 ms |
80112 KB |
Output is correct |
36 |
Correct |
193 ms |
79128 KB |
Output is correct |
37 |
Correct |
127 ms |
73404 KB |
Output is correct |
38 |
Correct |
199 ms |
78728 KB |
Output is correct |
39 |
Correct |
58 ms |
68008 KB |
Output is correct |
40 |
Correct |
214 ms |
78280 KB |
Output is correct |
41 |
Correct |
154 ms |
77032 KB |
Output is correct |
42 |
Correct |
195 ms |
79040 KB |
Output is correct |
43 |
Correct |
88 ms |
70320 KB |
Output is correct |
44 |
Correct |
190 ms |
78260 KB |
Output is correct |
45 |
Correct |
63 ms |
68368 KB |
Output is correct |
46 |
Correct |
189 ms |
78284 KB |
Output is correct |
47 |
Correct |
76 ms |
69316 KB |
Output is correct |
48 |
Correct |
189 ms |
78008 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
435 ms |
75856 KB |
Output is correct |
2 |
Correct |
474 ms |
81072 KB |
Output is correct |
3 |
Correct |
315 ms |
76588 KB |
Output is correct |
4 |
Correct |
466 ms |
81020 KB |
Output is correct |
5 |
Correct |
184 ms |
73040 KB |
Output is correct |
6 |
Correct |
448 ms |
81120 KB |
Output is correct |
7 |
Correct |
428 ms |
79188 KB |
Output is correct |
8 |
Correct |
454 ms |
81172 KB |
Output is correct |
9 |
Correct |
82 ms |
68472 KB |
Output is correct |
10 |
Correct |
495 ms |
81392 KB |
Output is correct |
11 |
Correct |
266 ms |
75980 KB |
Output is correct |
12 |
Correct |
446 ms |
81120 KB |
Output is correct |
13 |
Correct |
212 ms |
80396 KB |
Output is correct |
14 |
Correct |
206 ms |
80036 KB |
Output is correct |
15 |
Correct |
199 ms |
79172 KB |
Output is correct |
16 |
Correct |
222 ms |
79716 KB |
Output is correct |
17 |
Correct |
231 ms |
80844 KB |
Output is correct |
18 |
Correct |
218 ms |
80076 KB |
Output is correct |
19 |
Correct |
209 ms |
79940 KB |
Output is correct |
20 |
Correct |
206 ms |
79992 KB |
Output is correct |
21 |
Correct |
209 ms |
80292 KB |
Output is correct |
22 |
Correct |
213 ms |
80348 KB |
Output is correct |
23 |
Correct |
204 ms |
80212 KB |
Output is correct |
24 |
Correct |
191 ms |
78872 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
38 ms |
66168 KB |
Output is correct |
2 |
Correct |
37 ms |
66140 KB |
Output is correct |
3 |
Correct |
38 ms |
66236 KB |
Output is correct |
4 |
Correct |
37 ms |
66228 KB |
Output is correct |
5 |
Correct |
37 ms |
66128 KB |
Output is correct |
6 |
Correct |
41 ms |
66136 KB |
Output is correct |
7 |
Correct |
36 ms |
66140 KB |
Output is correct |
8 |
Correct |
37 ms |
66128 KB |
Output is correct |
9 |
Correct |
37 ms |
66004 KB |
Output is correct |
10 |
Correct |
38 ms |
66292 KB |
Output is correct |
11 |
Correct |
37 ms |
66136 KB |
Output is correct |
12 |
Correct |
36 ms |
66064 KB |
Output is correct |
13 |
Correct |
36 ms |
66132 KB |
Output is correct |
14 |
Correct |
36 ms |
65996 KB |
Output is correct |
15 |
Correct |
37 ms |
66128 KB |
Output is correct |
16 |
Correct |
45 ms |
66132 KB |
Output is correct |
17 |
Correct |
36 ms |
66132 KB |
Output is correct |
18 |
Correct |
36 ms |
66132 KB |
Output is correct |
19 |
Correct |
36 ms |
66140 KB |
Output is correct |
20 |
Correct |
37 ms |
66120 KB |
Output is correct |
21 |
Correct |
37 ms |
66132 KB |
Output is correct |
22 |
Correct |
37 ms |
66132 KB |
Output is correct |
23 |
Correct |
36 ms |
66220 KB |
Output is correct |
24 |
Correct |
36 ms |
66128 KB |
Output is correct |
25 |
Correct |
147 ms |
77380 KB |
Output is correct |
26 |
Correct |
51 ms |
67276 KB |
Output is correct |
27 |
Correct |
193 ms |
79544 KB |
Output is correct |
28 |
Correct |
196 ms |
79288 KB |
Output is correct |
29 |
Correct |
148 ms |
76964 KB |
Output is correct |
30 |
Correct |
145 ms |
76984 KB |
Output is correct |
31 |
Correct |
176 ms |
78764 KB |
Output is correct |
32 |
Correct |
195 ms |
79192 KB |
Output is correct |
33 |
Correct |
186 ms |
79036 KB |
Output is correct |
34 |
Correct |
116 ms |
72384 KB |
Output is correct |
35 |
Correct |
189 ms |
80112 KB |
Output is correct |
36 |
Correct |
193 ms |
79128 KB |
Output is correct |
37 |
Correct |
127 ms |
73404 KB |
Output is correct |
38 |
Correct |
199 ms |
78728 KB |
Output is correct |
39 |
Correct |
58 ms |
68008 KB |
Output is correct |
40 |
Correct |
214 ms |
78280 KB |
Output is correct |
41 |
Correct |
154 ms |
77032 KB |
Output is correct |
42 |
Correct |
195 ms |
79040 KB |
Output is correct |
43 |
Correct |
88 ms |
70320 KB |
Output is correct |
44 |
Correct |
190 ms |
78260 KB |
Output is correct |
45 |
Correct |
63 ms |
68368 KB |
Output is correct |
46 |
Correct |
189 ms |
78284 KB |
Output is correct |
47 |
Correct |
76 ms |
69316 KB |
Output is correct |
48 |
Correct |
189 ms |
78008 KB |
Output is correct |
49 |
Correct |
435 ms |
75856 KB |
Output is correct |
50 |
Correct |
474 ms |
81072 KB |
Output is correct |
51 |
Correct |
315 ms |
76588 KB |
Output is correct |
52 |
Correct |
466 ms |
81020 KB |
Output is correct |
53 |
Correct |
184 ms |
73040 KB |
Output is correct |
54 |
Correct |
448 ms |
81120 KB |
Output is correct |
55 |
Correct |
428 ms |
79188 KB |
Output is correct |
56 |
Correct |
454 ms |
81172 KB |
Output is correct |
57 |
Correct |
82 ms |
68472 KB |
Output is correct |
58 |
Correct |
495 ms |
81392 KB |
Output is correct |
59 |
Correct |
266 ms |
75980 KB |
Output is correct |
60 |
Correct |
446 ms |
81120 KB |
Output is correct |
61 |
Correct |
212 ms |
80396 KB |
Output is correct |
62 |
Correct |
206 ms |
80036 KB |
Output is correct |
63 |
Correct |
199 ms |
79172 KB |
Output is correct |
64 |
Correct |
222 ms |
79716 KB |
Output is correct |
65 |
Correct |
231 ms |
80844 KB |
Output is correct |
66 |
Correct |
218 ms |
80076 KB |
Output is correct |
67 |
Correct |
209 ms |
79940 KB |
Output is correct |
68 |
Correct |
206 ms |
79992 KB |
Output is correct |
69 |
Correct |
209 ms |
80292 KB |
Output is correct |
70 |
Correct |
213 ms |
80348 KB |
Output is correct |
71 |
Correct |
204 ms |
80212 KB |
Output is correct |
72 |
Correct |
191 ms |
78872 KB |
Output is correct |
73 |
Correct |
727 ms |
92896 KB |
Output is correct |
74 |
Correct |
546 ms |
82616 KB |
Output is correct |
75 |
Correct |
650 ms |
92188 KB |
Output is correct |
76 |
Correct |
856 ms |
97892 KB |
Output is correct |
77 |
Correct |
395 ms |
85496 KB |
Output is correct |
78 |
Correct |
714 ms |
92888 KB |
Output is correct |
79 |
Correct |
914 ms |
95092 KB |
Output is correct |
80 |
Correct |
919 ms |
98152 KB |
Output is correct |
81 |
Correct |
291 ms |
82300 KB |
Output is correct |
82 |
Correct |
691 ms |
89280 KB |
Output is correct |
83 |
Correct |
639 ms |
91344 KB |
Output is correct |
84 |
Correct |
901 ms |
97020 KB |
Output is correct |
85 |
Correct |
439 ms |
89540 KB |
Output is correct |
86 |
Correct |
608 ms |
95176 KB |
Output is correct |
87 |
Correct |
252 ms |
81844 KB |
Output is correct |
88 |
Correct |
590 ms |
94724 KB |
Output is correct |
89 |
Correct |
495 ms |
93632 KB |
Output is correct |
90 |
Correct |
567 ms |
94876 KB |
Output is correct |
91 |
Correct |
399 ms |
85660 KB |
Output is correct |
92 |
Correct |
600 ms |
95144 KB |
Output is correct |
93 |
Correct |
274 ms |
83312 KB |
Output is correct |
94 |
Correct |
630 ms |
95172 KB |
Output is correct |
95 |
Correct |
305 ms |
84452 KB |
Output is correct |
96 |
Correct |
560 ms |
93808 KB |
Output is correct |