#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
void print() {cerr << ']' << endl;}
template<typename Head, typename... Tail> void print(Head H, Tail... T) {cerr << ' ' << H; if(sizeof...(T)) cerr << ','; print(T...); }
template<typename T> ostream& operator << (ostream& os, vector<T> v){os << "["; bool first = 1; for(auto x : v) {if(!first) os << ", "; os << x; first = 0;} os << "]"; return os;}
template<typename A, typename B> ostream& operator <<(ostream& os,pair<A, B> p) {return os << "(" << p.first << ", " << p.second << ")"; return os;}
template<typename A, typename B, typename C> ostream& operator << (ostream& os, tuple<A, B, C> a) {os << '(' << get<0>(a) << ", " << get<1>(a) << ", " << get<2>(a) << ")"; return os;}
template<typename A, size_t S> ostream& operator << (ostream& os, array<A, S> a) {os << "["; bool first = 1; for(auto x : a) {if(!first) os << ", "; os << x; first = 0;} os << "]"; return os;}
template<typename A> ostream& operator << (ostream& os, set<A> s) {os << "["; bool first = 1; for(auto x : s) {if(!first) os << ", "; os << x; first = 0;} os << "]"; return os;}
template<typename A, typename B> ostream& operator << (ostream& os, map<A, B> m) {os << "["; bool first = 1; for(auto x : m) {if(!first) os << ", "; os << x; first = 0;} os << "]"; return os;}
#define dbg(...) cerr << '[' << #__VA_ARGS__ << ":", print(__VA_ARGS__);
#else
#define dbg(...)
#endif // LOCAL
#define ll long long
#define vt vector
#define pb push_back
#define sz(x) int((x).size())
const int INF = 1e9 + 5;
struct Op
{
int mn, mx;
Op()
{
mn = INF;
mx = -INF;
}
Op(int a, int b)
{
mn = a;
mx = b;
}
Op& operator += (Op a)
{
mn = min(mn, a.mn);
mx = max(mx, a.mx);
return *this;
}
};
struct Node
{
int mn, mx, best;
Node()
{
mn = INF;
mx = -INF;
best = -INF;
}
Node(int _mn, int _mx, int _best = -INF)
{
mn = _mn;
mx = _mx;
best = _best;
}
void apply(Op op)
{
if(mn == INF) return;
best = max(best, max(mx - op.mn, op.mx - mn));
}
};
ostream& operator << (ostream& os, Node n) {return os << "(" << n.mn << ", " << n.mx << " -> " << n.best << ")";}
ostream& operator << (ostream& os, Op n) {return os << "(" << n.mn << ", " << n.mx << ")";}
bool operator != (Op a, Op b){ return a.mn != b.mn || a.mx != b.mx; }
bool operator == (Node a, Node b) {return a.mn == b.mn && a.mx == b.mx && a.best == b.best;}
Node operator + (Node a, Node b)
{
Node ret;
if(a == Node()) ret = b;
else if(b == Node()) ret = a;
else
{
ret.mn = min(a.mn, b.mn);
ret.mx = max(a.mx, b.mx);
ret.best = max(a.best, b.best);
}
return ret;
}
struct SegTree
{
vt<Node> S;
vt<Op> lazy;
int N;
SegTree(int _N)
{
N = 1;
while(N < _N) N *= 2;
S.resize(2 * N);
lazy.resize(2 * N);
}
void push(int i)
{
if(lazy[i] != Op())
{
S[i].apply(lazy[i]);
if(i < N)
{
lazy[2 * i] += lazy[i];
lazy[2 * i + 1] += lazy[i];
}
lazy[i] = Op();
}
}
int qry(int l, int r, int a, int b, int i)
{
push(i);
if(l <= a && b <= r) return S[i].best;
if(r < a || b < l) return -INF;
int m = (a + b) / 2;
return max(qry(l, r, a, m, 2 * i), qry(l, r, m + 1, b, 2 * i + 1));
}
int qry(int l, int r) {return qry(l, r, 1, N, 1);}
void apply(int l, int r, Op o, int a, int b, int i)
{
push(i);
if(l <= a && b <= r)
{
lazy[i] += o;
push(i);
return;
}
if(r < a || b < l) return;
int m = (a + b) / 2;
apply(l, r, o, a, m, 2 * i);
apply(l, r, o, m + 1, b, 2 * i + 1);
S[i] = S[2 * i] + S[2 * i + 1];
}
void apply(int l, int r, Op o) {apply(l, r, o, 1, N, 1);}
void upd(int i, Node n)
{
qry(i, i); //Clear lazy
int u = i + N - 1;
S[u].mx = n.mx;
S[u].mn = n.mn;
//dbg(u, S[u]);
for(u /= 2; u > 0; u /= 2)
{
S[u] = S[2 * u] + S[2 * u + 1];
}
}
};
int N, Q;
vt<int> H, A, B;
vt<pair<int, int>> queries;
vt<int> solve()
{
vt<vt<int>> act(N + 1), deact(N + 1), qry(N + 1);
for(int i = 0; i < N; i++)
{
act[min(N, i + A[i])].pb(i);
deact[min(N, i + B[i] + 1)].pb(i);
}
vt<int> ans(Q);
vt<int> lb(Q);
for(int i = 0; i < Q; i++)
{
auto [L, R] = queries[i];
qry[R].pb(i);
lb[i] = L;
}
SegTree s(N);
for(int i = 0; i < N; i++)
{
for(int x : deact[i]) s.upd(x + 1, Node());
for(int x : act[i]) s.upd(x + 1, Node(H[x], H[x]));
//Apply myself
s.apply(1 + max(0, i - B[i]), 1 + max(-1, i - A[i]), Op(H[i], H[i]));
//dbg(s.S);
for(int x : qry[i]) ans[x] = s.qry(1 + lb[x], i + 1);
}
for(int& x : ans) x = max(-1, x);
return ans;
}
vt<int> brute()
{
vt<int> ans(Q);
for(int i = 0; i < Q; i++)
{
int best = -1;
for(int j = queries[i].first; j <= queries[i].second; j++)
{
for(int k = j + 1; k <= queries[i].second; k++)
{
if(j + A[j] <= k && k <= j + B[j] && k - B[k] <= j && j <= k - A[k])
{
best = max(best, abs(H[j] - H[k]));
}
}
}
ans[i] = best;
}
return ans;
}
//#define TESTING
random_device rd;
mt19937 rng(rd());
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
#ifdef TESTING
while(true)
{
N = uid(2, 100);
H = vt<int>(N);
A = vt<int>(N);
B = vt<int>(N);
for(int& x : H) x = uid(1, 1000);
for(int i = 0; i < N; i++)
{
A[i] = uid(1, N - 1);
B[i] = A[i] + uid(0, N - 1 - A[i]);
}
Q = uid(1, 100);
queries = vt<pair<int, int>>(Q);
for(int i = 0; i < Q; i++)
{
queries[i].first = uid(0, N - 1);
queries[i].second = queries[i].first + uid(0, N - 1 - queries[i].first);
}
if(solve() != brute())
{
dbg(solve());
dbg(brute());
cout << N << "\n";
for(int i = 0; i < N; i++) cout << H[i] << " " << A[i] << " " << B[i] << "\n";
cout << Q << "\n";
for(auto& [a, b] : queries) cout << 1 + a << " " << 1 + b << "\n";
exit(0);
}
}
#else
cin >> N;
H = vt<int>(N);
A = vt<int>(N);
B = vt<int>(N);
for(int i = 0; i < N; i++) cin >> H[i] >> A[i] >> B[i];
cin >> Q;
queries = vt<pair<int, int>>(Q);
for(int i = 0; i < Q; i++)
{
cin >> queries[i].first >> queries[i].second, --queries[i].first, --queries[i].second;
}
for(int x : solve()) cout << x << "\n";
#endif // TESTING
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
392 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
0 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
392 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
0 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
75 ms |
4364 KB |
Output is correct |
26 |
Correct |
10 ms |
1240 KB |
Output is correct |
27 |
Correct |
91 ms |
7656 KB |
Output is correct |
28 |
Correct |
94 ms |
7784 KB |
Output is correct |
29 |
Correct |
64 ms |
5524 KB |
Output is correct |
30 |
Correct |
63 ms |
5328 KB |
Output is correct |
31 |
Correct |
76 ms |
6788 KB |
Output is correct |
32 |
Correct |
104 ms |
7728 KB |
Output is correct |
33 |
Correct |
84 ms |
7232 KB |
Output is correct |
34 |
Correct |
46 ms |
4064 KB |
Output is correct |
35 |
Correct |
90 ms |
7644 KB |
Output is correct |
36 |
Correct |
120 ms |
7780 KB |
Output is correct |
37 |
Correct |
52 ms |
4192 KB |
Output is correct |
38 |
Correct |
87 ms |
6836 KB |
Output is correct |
39 |
Correct |
14 ms |
1620 KB |
Output is correct |
40 |
Correct |
91 ms |
6864 KB |
Output is correct |
41 |
Correct |
63 ms |
5156 KB |
Output is correct |
42 |
Correct |
85 ms |
6776 KB |
Output is correct |
43 |
Correct |
30 ms |
2660 KB |
Output is correct |
44 |
Correct |
89 ms |
6776 KB |
Output is correct |
45 |
Correct |
16 ms |
1620 KB |
Output is correct |
46 |
Correct |
88 ms |
6964 KB |
Output is correct |
47 |
Correct |
23 ms |
2160 KB |
Output is correct |
48 |
Correct |
98 ms |
6912 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
291 ms |
29688 KB |
Output is correct |
2 |
Correct |
316 ms |
36312 KB |
Output is correct |
3 |
Correct |
213 ms |
28464 KB |
Output is correct |
4 |
Correct |
312 ms |
36416 KB |
Output is correct |
5 |
Correct |
118 ms |
17248 KB |
Output is correct |
6 |
Correct |
327 ms |
36324 KB |
Output is correct |
7 |
Correct |
259 ms |
32704 KB |
Output is correct |
8 |
Correct |
295 ms |
36336 KB |
Output is correct |
9 |
Correct |
43 ms |
5712 KB |
Output is correct |
10 |
Correct |
317 ms |
36416 KB |
Output is correct |
11 |
Correct |
190 ms |
21432 KB |
Output is correct |
12 |
Correct |
317 ms |
36312 KB |
Output is correct |
13 |
Correct |
218 ms |
33600 KB |
Output is correct |
14 |
Correct |
210 ms |
33708 KB |
Output is correct |
15 |
Correct |
201 ms |
33736 KB |
Output is correct |
16 |
Correct |
202 ms |
33948 KB |
Output is correct |
17 |
Correct |
236 ms |
33624 KB |
Output is correct |
18 |
Correct |
221 ms |
34028 KB |
Output is correct |
19 |
Correct |
213 ms |
33744 KB |
Output is correct |
20 |
Correct |
204 ms |
33616 KB |
Output is correct |
21 |
Correct |
205 ms |
33872 KB |
Output is correct |
22 |
Correct |
201 ms |
33700 KB |
Output is correct |
23 |
Correct |
206 ms |
33672 KB |
Output is correct |
24 |
Correct |
213 ms |
33768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
392 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
0 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
75 ms |
4364 KB |
Output is correct |
26 |
Correct |
10 ms |
1240 KB |
Output is correct |
27 |
Correct |
91 ms |
7656 KB |
Output is correct |
28 |
Correct |
94 ms |
7784 KB |
Output is correct |
29 |
Correct |
64 ms |
5524 KB |
Output is correct |
30 |
Correct |
63 ms |
5328 KB |
Output is correct |
31 |
Correct |
76 ms |
6788 KB |
Output is correct |
32 |
Correct |
104 ms |
7728 KB |
Output is correct |
33 |
Correct |
84 ms |
7232 KB |
Output is correct |
34 |
Correct |
46 ms |
4064 KB |
Output is correct |
35 |
Correct |
90 ms |
7644 KB |
Output is correct |
36 |
Correct |
120 ms |
7780 KB |
Output is correct |
37 |
Correct |
52 ms |
4192 KB |
Output is correct |
38 |
Correct |
87 ms |
6836 KB |
Output is correct |
39 |
Correct |
14 ms |
1620 KB |
Output is correct |
40 |
Correct |
91 ms |
6864 KB |
Output is correct |
41 |
Correct |
63 ms |
5156 KB |
Output is correct |
42 |
Correct |
85 ms |
6776 KB |
Output is correct |
43 |
Correct |
30 ms |
2660 KB |
Output is correct |
44 |
Correct |
89 ms |
6776 KB |
Output is correct |
45 |
Correct |
16 ms |
1620 KB |
Output is correct |
46 |
Correct |
88 ms |
6964 KB |
Output is correct |
47 |
Correct |
23 ms |
2160 KB |
Output is correct |
48 |
Correct |
98 ms |
6912 KB |
Output is correct |
49 |
Correct |
291 ms |
29688 KB |
Output is correct |
50 |
Correct |
316 ms |
36312 KB |
Output is correct |
51 |
Correct |
213 ms |
28464 KB |
Output is correct |
52 |
Correct |
312 ms |
36416 KB |
Output is correct |
53 |
Correct |
118 ms |
17248 KB |
Output is correct |
54 |
Correct |
327 ms |
36324 KB |
Output is correct |
55 |
Correct |
259 ms |
32704 KB |
Output is correct |
56 |
Correct |
295 ms |
36336 KB |
Output is correct |
57 |
Correct |
43 ms |
5712 KB |
Output is correct |
58 |
Correct |
317 ms |
36416 KB |
Output is correct |
59 |
Correct |
190 ms |
21432 KB |
Output is correct |
60 |
Correct |
317 ms |
36312 KB |
Output is correct |
61 |
Correct |
218 ms |
33600 KB |
Output is correct |
62 |
Correct |
210 ms |
33708 KB |
Output is correct |
63 |
Correct |
201 ms |
33736 KB |
Output is correct |
64 |
Correct |
202 ms |
33948 KB |
Output is correct |
65 |
Correct |
236 ms |
33624 KB |
Output is correct |
66 |
Correct |
221 ms |
34028 KB |
Output is correct |
67 |
Correct |
213 ms |
33744 KB |
Output is correct |
68 |
Correct |
204 ms |
33616 KB |
Output is correct |
69 |
Correct |
205 ms |
33872 KB |
Output is correct |
70 |
Correct |
201 ms |
33700 KB |
Output is correct |
71 |
Correct |
206 ms |
33672 KB |
Output is correct |
72 |
Correct |
213 ms |
33768 KB |
Output is correct |
73 |
Correct |
431 ms |
40312 KB |
Output is correct |
74 |
Correct |
344 ms |
36952 KB |
Output is correct |
75 |
Correct |
385 ms |
36788 KB |
Output is correct |
76 |
Correct |
574 ms |
45096 KB |
Output is correct |
77 |
Correct |
245 ms |
23116 KB |
Output is correct |
78 |
Correct |
445 ms |
42432 KB |
Output is correct |
79 |
Correct |
501 ms |
41460 KB |
Output is correct |
80 |
Correct |
550 ms |
45156 KB |
Output is correct |
81 |
Correct |
179 ms |
12468 KB |
Output is correct |
82 |
Correct |
400 ms |
40796 KB |
Output is correct |
83 |
Correct |
429 ms |
29628 KB |
Output is correct |
84 |
Correct |
542 ms |
45088 KB |
Output is correct |
85 |
Correct |
310 ms |
38972 KB |
Output is correct |
86 |
Correct |
392 ms |
42580 KB |
Output is correct |
87 |
Correct |
224 ms |
35060 KB |
Output is correct |
88 |
Correct |
384 ms |
42932 KB |
Output is correct |
89 |
Correct |
353 ms |
40284 KB |
Output is correct |
90 |
Correct |
386 ms |
43072 KB |
Output is correct |
91 |
Correct |
286 ms |
36588 KB |
Output is correct |
92 |
Correct |
372 ms |
42424 KB |
Output is correct |
93 |
Correct |
235 ms |
35028 KB |
Output is correct |
94 |
Correct |
373 ms |
42608 KB |
Output is correct |
95 |
Correct |
258 ms |
36124 KB |
Output is correct |
96 |
Correct |
376 ms |
42524 KB |
Output is correct |