#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define uint unsigned int
using namespace std;
const int INF = 1e9;
struct Query {
int l, pos;
};
vector <int> h, a, b;
vector <int> l, r;
vector <int> sol;
struct Event {
int x, type, pos;
bool operator <(const Event &other) const {
if(x == other.x) return type < other.type;
return x < other.x;
}
};
struct Node {
int val, mx, lazy;
Node(int _val = INF, int _mx = -INF, int _lazy = -INF) : val(_val), mx(_mx), lazy(_lazy) {}
};
struct SegTree {
vector <Node> aint;
int n, sz;
SegTree(int _n) {
n = _n, sz = 1;
while(sz < 2 * n) {
sz *= 2;
}
aint.resize(sz + 1);
}
inline void push(int nod) {
if(2 * nod + 1 <= sz) {
aint[2 * nod].lazy = max(aint[2 * nod].lazy, aint[nod].lazy);
aint[2 * nod + 1].lazy = max(aint[2 * nod + 1].lazy, aint[nod].lazy);
}
aint[nod].mx = max(aint[nod].mx, aint[nod].lazy - aint[nod].val);
aint[nod].lazy = -INF;
}
inline void combine(Node a, Node b, Node &ans) {
ans.val = min(a.val, b.val);
ans.mx = max(ans.mx, max(a.mx, b.mx));
}
void update(int nod, int left, int right, int pos, int val) {
push(nod);
if(left == right) {
aint[nod].val = val;
}
else {
int mid = (left + right) / 2;
if(pos <= mid) update(2 * nod, left, mid, pos, val);
else update(2 * nod + 1, mid + 1, right, pos, val);
combine(aint[2 * nod], aint[2 * nod + 1], aint[nod]);
}
}
void update(int nod, int left, int right, int l, int r, int lazy) {
push(nod);
if(l > right || r < left || l > r) return ;
if(l <= left && right <= r) {
aint[nod].lazy = max(aint[nod].lazy, lazy);
push(nod);
return ;
}
int mid = (left + right) / 2;
update(2 * nod, left, mid, l, r, lazy);
update(2 * nod + 1, mid + 1, right, l, r, lazy);
combine(aint[2 * nod], aint[2 * nod + 1], aint[nod]);
}
int query(int nod, int left, int right, int l, int r) {
push(nod);
if(l > right || r < left || l > r) return -INF;
if(l <= left && right <= r) {
return aint[nod].mx;
}
int mid = (left + right) / 2;
int ans = max(query(2 * nod, left, mid, l, r), query(2 * nod + 1, mid + 1, right, l, r));
combine(aint[2 * nod], aint[2 * nod + 1], aint[nod]);
return ans;
}
};
inline void solve(int n, int q) {
vector < vector <Query> > qry(n + 1);
int i;
for(i = 1; i <= q; i++) {
qry[r[i]].push_back({l[i], i});
}
vector <Event> evs;
for(i = 1; i <= n; i++) {
evs.push_back({i + a[i], -1, i});
evs.push_back({i + b[i] + 1, 0, i});
evs.push_back({i, 1, i});
}
sort(evs.begin(), evs.end());
SegTree st(n);
i = 0;
while(i < 3 * n) {
int j = i;
while(j < 3 * n && evs[i].x == evs[j].x) {
//cerr << evs[j].x << " " << evs[j].pos << " " << evs[j].type << "\n";
if(evs[j].type == -1) {
st.update(1, 1, n, evs[j].pos, h[evs[j].pos]);
}
if(evs[j].type == 0) {
st.update(1, 1, n, evs[j].pos, INF);
}
if(evs[j].type == 1) {
//cerr << evs[j].pos << " " << max(1, evs[j].pos - b[evs[j].pos]) << " " << min(n, evs[j].pos - a[evs[j].pos]) << "\n";
st.update(1, 1, n, max(1, evs[j].pos - b[evs[j].pos]), min(n, evs[j].pos - a[evs[j].pos]), h[evs[j].pos]);
//cerr << evs[j].pos << " " << evs[j].type << "\n";
//cerr << st.query(1, 1, n, 1, evs[j].x) << " " << max(1, evs[j].pos - b[evs[j].pos]) << " " << min(n, evs[j].pos - a[evs[j].pos]) << "\n";
}
j++;
}
if(evs[i].x >= 1 && evs[i].x <= n) {
for(auto it : qry[evs[i].x]) {
int cur = st.query(1, 1, n, it.l, evs[i].x);
sol[it.pos] = max(sol[it.pos], cur);
}
}
i = j;
}
}
int main() {
#ifdef HOME
ifstream cin("A.in");
ofstream cout("A.out");
#endif
int i, n, q;
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n;
h.resize(n + 1), a.resize(n + 1), b.resize(n + 1);
for(i = 1; i <= n; i++) {
cin >> h[i] >> a[i] >> b[i];
}
cin >> q;
l.resize(q + 1), r.resize(q + 1);
for(i = 1; i <= q; i++) {
cin >> l[i] >> r[i];
}
sol.resize(q + 1, -1);
solve(n, q);
for(i = 1; i < n - i + 1; i++) {
swap(h[i], h[n - i + 1]);
swap(a[i], a[n - i + 1]);
swap(b[i], b[n - i + 1]);
}
for(i = 1; i <= q; i++) {
l[i] = n - l[i] + 1;
r[i] = n - r[i] + 1;
swap(l[i], r[i]);
}
solve(n, q);
for(i = 1; i <= q; i++) {
cout << max(sol[i], -1) << "\n";
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
6 ms |
376 KB |
Output is correct |
3 |
Correct |
6 ms |
376 KB |
Output is correct |
4 |
Correct |
6 ms |
376 KB |
Output is correct |
5 |
Correct |
6 ms |
376 KB |
Output is correct |
6 |
Correct |
6 ms |
376 KB |
Output is correct |
7 |
Correct |
6 ms |
376 KB |
Output is correct |
8 |
Correct |
6 ms |
376 KB |
Output is correct |
9 |
Correct |
6 ms |
376 KB |
Output is correct |
10 |
Correct |
6 ms |
376 KB |
Output is correct |
11 |
Correct |
6 ms |
376 KB |
Output is correct |
12 |
Correct |
6 ms |
408 KB |
Output is correct |
13 |
Correct |
6 ms |
376 KB |
Output is correct |
14 |
Correct |
6 ms |
376 KB |
Output is correct |
15 |
Correct |
6 ms |
376 KB |
Output is correct |
16 |
Correct |
6 ms |
376 KB |
Output is correct |
17 |
Correct |
6 ms |
376 KB |
Output is correct |
18 |
Correct |
6 ms |
376 KB |
Output is correct |
19 |
Correct |
6 ms |
376 KB |
Output is correct |
20 |
Correct |
6 ms |
376 KB |
Output is correct |
21 |
Correct |
6 ms |
376 KB |
Output is correct |
22 |
Correct |
6 ms |
376 KB |
Output is correct |
23 |
Correct |
6 ms |
376 KB |
Output is correct |
24 |
Correct |
6 ms |
380 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
6 ms |
376 KB |
Output is correct |
3 |
Correct |
6 ms |
376 KB |
Output is correct |
4 |
Correct |
6 ms |
376 KB |
Output is correct |
5 |
Correct |
6 ms |
376 KB |
Output is correct |
6 |
Correct |
6 ms |
376 KB |
Output is correct |
7 |
Correct |
6 ms |
376 KB |
Output is correct |
8 |
Correct |
6 ms |
376 KB |
Output is correct |
9 |
Correct |
6 ms |
376 KB |
Output is correct |
10 |
Correct |
6 ms |
376 KB |
Output is correct |
11 |
Correct |
6 ms |
376 KB |
Output is correct |
12 |
Correct |
6 ms |
408 KB |
Output is correct |
13 |
Correct |
6 ms |
376 KB |
Output is correct |
14 |
Correct |
6 ms |
376 KB |
Output is correct |
15 |
Correct |
6 ms |
376 KB |
Output is correct |
16 |
Correct |
6 ms |
376 KB |
Output is correct |
17 |
Correct |
6 ms |
376 KB |
Output is correct |
18 |
Correct |
6 ms |
376 KB |
Output is correct |
19 |
Correct |
6 ms |
376 KB |
Output is correct |
20 |
Correct |
6 ms |
376 KB |
Output is correct |
21 |
Correct |
6 ms |
376 KB |
Output is correct |
22 |
Correct |
6 ms |
376 KB |
Output is correct |
23 |
Correct |
6 ms |
376 KB |
Output is correct |
24 |
Correct |
6 ms |
380 KB |
Output is correct |
25 |
Correct |
158 ms |
5372 KB |
Output is correct |
26 |
Correct |
26 ms |
1192 KB |
Output is correct |
27 |
Correct |
238 ms |
7248 KB |
Output is correct |
28 |
Correct |
232 ms |
7160 KB |
Output is correct |
29 |
Correct |
164 ms |
5544 KB |
Output is correct |
30 |
Correct |
189 ms |
5232 KB |
Output is correct |
31 |
Correct |
182 ms |
6744 KB |
Output is correct |
32 |
Correct |
258 ms |
7320 KB |
Output is correct |
33 |
Correct |
224 ms |
7136 KB |
Output is correct |
34 |
Correct |
128 ms |
3832 KB |
Output is correct |
35 |
Correct |
243 ms |
7556 KB |
Output is correct |
36 |
Correct |
238 ms |
7160 KB |
Output is correct |
37 |
Correct |
151 ms |
4400 KB |
Output is correct |
38 |
Correct |
250 ms |
7160 KB |
Output is correct |
39 |
Correct |
49 ms |
1596 KB |
Output is correct |
40 |
Correct |
254 ms |
7288 KB |
Output is correct |
41 |
Correct |
168 ms |
5852 KB |
Output is correct |
42 |
Correct |
250 ms |
7288 KB |
Output is correct |
43 |
Correct |
79 ms |
2944 KB |
Output is correct |
44 |
Correct |
258 ms |
7288 KB |
Output is correct |
45 |
Correct |
50 ms |
1784 KB |
Output is correct |
46 |
Correct |
248 ms |
7160 KB |
Output is correct |
47 |
Correct |
65 ms |
2348 KB |
Output is correct |
48 |
Correct |
242 ms |
7376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
690 ms |
29572 KB |
Output is correct |
2 |
Correct |
741 ms |
31284 KB |
Output is correct |
3 |
Correct |
486 ms |
19888 KB |
Output is correct |
4 |
Correct |
693 ms |
31328 KB |
Output is correct |
5 |
Correct |
282 ms |
15008 KB |
Output is correct |
6 |
Correct |
736 ms |
31336 KB |
Output is correct |
7 |
Correct |
588 ms |
22876 KB |
Output is correct |
8 |
Correct |
733 ms |
31476 KB |
Output is correct |
9 |
Correct |
91 ms |
4756 KB |
Output is correct |
10 |
Correct |
738 ms |
31332 KB |
Output is correct |
11 |
Correct |
381 ms |
18168 KB |
Output is correct |
12 |
Correct |
760 ms |
31460 KB |
Output is correct |
13 |
Correct |
505 ms |
31332 KB |
Output is correct |
14 |
Correct |
484 ms |
31336 KB |
Output is correct |
15 |
Correct |
485 ms |
31328 KB |
Output is correct |
16 |
Correct |
456 ms |
31144 KB |
Output is correct |
17 |
Correct |
500 ms |
31200 KB |
Output is correct |
18 |
Correct |
495 ms |
31276 KB |
Output is correct |
19 |
Correct |
488 ms |
31340 KB |
Output is correct |
20 |
Correct |
496 ms |
31208 KB |
Output is correct |
21 |
Correct |
468 ms |
31332 KB |
Output is correct |
22 |
Correct |
476 ms |
31208 KB |
Output is correct |
23 |
Correct |
489 ms |
31204 KB |
Output is correct |
24 |
Correct |
450 ms |
31208 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
6 ms |
376 KB |
Output is correct |
3 |
Correct |
6 ms |
376 KB |
Output is correct |
4 |
Correct |
6 ms |
376 KB |
Output is correct |
5 |
Correct |
6 ms |
376 KB |
Output is correct |
6 |
Correct |
6 ms |
376 KB |
Output is correct |
7 |
Correct |
6 ms |
376 KB |
Output is correct |
8 |
Correct |
6 ms |
376 KB |
Output is correct |
9 |
Correct |
6 ms |
376 KB |
Output is correct |
10 |
Correct |
6 ms |
376 KB |
Output is correct |
11 |
Correct |
6 ms |
376 KB |
Output is correct |
12 |
Correct |
6 ms |
408 KB |
Output is correct |
13 |
Correct |
6 ms |
376 KB |
Output is correct |
14 |
Correct |
6 ms |
376 KB |
Output is correct |
15 |
Correct |
6 ms |
376 KB |
Output is correct |
16 |
Correct |
6 ms |
376 KB |
Output is correct |
17 |
Correct |
6 ms |
376 KB |
Output is correct |
18 |
Correct |
6 ms |
376 KB |
Output is correct |
19 |
Correct |
6 ms |
376 KB |
Output is correct |
20 |
Correct |
6 ms |
376 KB |
Output is correct |
21 |
Correct |
6 ms |
376 KB |
Output is correct |
22 |
Correct |
6 ms |
376 KB |
Output is correct |
23 |
Correct |
6 ms |
376 KB |
Output is correct |
24 |
Correct |
6 ms |
380 KB |
Output is correct |
25 |
Correct |
158 ms |
5372 KB |
Output is correct |
26 |
Correct |
26 ms |
1192 KB |
Output is correct |
27 |
Correct |
238 ms |
7248 KB |
Output is correct |
28 |
Correct |
232 ms |
7160 KB |
Output is correct |
29 |
Correct |
164 ms |
5544 KB |
Output is correct |
30 |
Correct |
189 ms |
5232 KB |
Output is correct |
31 |
Correct |
182 ms |
6744 KB |
Output is correct |
32 |
Correct |
258 ms |
7320 KB |
Output is correct |
33 |
Correct |
224 ms |
7136 KB |
Output is correct |
34 |
Correct |
128 ms |
3832 KB |
Output is correct |
35 |
Correct |
243 ms |
7556 KB |
Output is correct |
36 |
Correct |
238 ms |
7160 KB |
Output is correct |
37 |
Correct |
151 ms |
4400 KB |
Output is correct |
38 |
Correct |
250 ms |
7160 KB |
Output is correct |
39 |
Correct |
49 ms |
1596 KB |
Output is correct |
40 |
Correct |
254 ms |
7288 KB |
Output is correct |
41 |
Correct |
168 ms |
5852 KB |
Output is correct |
42 |
Correct |
250 ms |
7288 KB |
Output is correct |
43 |
Correct |
79 ms |
2944 KB |
Output is correct |
44 |
Correct |
258 ms |
7288 KB |
Output is correct |
45 |
Correct |
50 ms |
1784 KB |
Output is correct |
46 |
Correct |
248 ms |
7160 KB |
Output is correct |
47 |
Correct |
65 ms |
2348 KB |
Output is correct |
48 |
Correct |
242 ms |
7376 KB |
Output is correct |
49 |
Correct |
690 ms |
29572 KB |
Output is correct |
50 |
Correct |
741 ms |
31284 KB |
Output is correct |
51 |
Correct |
486 ms |
19888 KB |
Output is correct |
52 |
Correct |
693 ms |
31328 KB |
Output is correct |
53 |
Correct |
282 ms |
15008 KB |
Output is correct |
54 |
Correct |
736 ms |
31336 KB |
Output is correct |
55 |
Correct |
588 ms |
22876 KB |
Output is correct |
56 |
Correct |
733 ms |
31476 KB |
Output is correct |
57 |
Correct |
91 ms |
4756 KB |
Output is correct |
58 |
Correct |
738 ms |
31332 KB |
Output is correct |
59 |
Correct |
381 ms |
18168 KB |
Output is correct |
60 |
Correct |
760 ms |
31460 KB |
Output is correct |
61 |
Correct |
505 ms |
31332 KB |
Output is correct |
62 |
Correct |
484 ms |
31336 KB |
Output is correct |
63 |
Correct |
485 ms |
31328 KB |
Output is correct |
64 |
Correct |
456 ms |
31144 KB |
Output is correct |
65 |
Correct |
500 ms |
31200 KB |
Output is correct |
66 |
Correct |
495 ms |
31276 KB |
Output is correct |
67 |
Correct |
488 ms |
31340 KB |
Output is correct |
68 |
Correct |
496 ms |
31208 KB |
Output is correct |
69 |
Correct |
468 ms |
31332 KB |
Output is correct |
70 |
Correct |
476 ms |
31208 KB |
Output is correct |
71 |
Correct |
489 ms |
31204 KB |
Output is correct |
72 |
Correct |
450 ms |
31208 KB |
Output is correct |
73 |
Correct |
1035 ms |
36480 KB |
Output is correct |
74 |
Correct |
757 ms |
32200 KB |
Output is correct |
75 |
Correct |
974 ms |
28400 KB |
Output is correct |
76 |
Correct |
1276 ms |
40620 KB |
Output is correct |
77 |
Correct |
570 ms |
21152 KB |
Output is correct |
78 |
Correct |
1036 ms |
37864 KB |
Output is correct |
79 |
Correct |
1147 ms |
31920 KB |
Output is correct |
80 |
Correct |
1237 ms |
40724 KB |
Output is correct |
81 |
Correct |
419 ms |
12100 KB |
Output is correct |
82 |
Correct |
1022 ms |
36104 KB |
Output is correct |
83 |
Correct |
851 ms |
26768 KB |
Output is correct |
84 |
Correct |
1235 ms |
40808 KB |
Output is correct |
85 |
Correct |
797 ms |
36960 KB |
Output is correct |
86 |
Correct |
969 ms |
40552 KB |
Output is correct |
87 |
Correct |
556 ms |
32744 KB |
Output is correct |
88 |
Correct |
1035 ms |
40416 KB |
Output is correct |
89 |
Correct |
863 ms |
38340 KB |
Output is correct |
90 |
Correct |
1010 ms |
40544 KB |
Output is correct |
91 |
Correct |
672 ms |
34680 KB |
Output is correct |
92 |
Correct |
1053 ms |
40516 KB |
Output is correct |
93 |
Correct |
541 ms |
33128 KB |
Output is correct |
94 |
Correct |
995 ms |
40548 KB |
Output is correct |
95 |
Correct |
608 ms |
33888 KB |
Output is correct |
96 |
Correct |
954 ms |
40628 KB |
Output is correct |