#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
template <class T>
void read(T &x)
{
x = 0;
register int c;
while ((c = getchar()) && (c > '9' || c < '0'))
;
for (; c >= '0' && c <= '9'; c = getchar())
x = x * 10 + c - '0';
}
constexpr bool typetest = 0;
constexpr int N = 2e5 + 5;
constexpr int Inf = 1e9 + 7;
// SegmentTree kĩ thuật thượng thừa
// Lả lướt với SegmetTree
struct SegmentTree
{
int st[N * 4], maxn[N * 4], minn[N * 4], n;
SegmentTree()
{
}
void Assign(int n)
{
this->n = n;
fill_n(maxn, N * 4, -Inf);
fill_n(minn, N * 4, Inf);
fill_n(st, N * 4, -Inf);
}
void Push(int id)
{
if (minn[id] != Inf)
{
minn[id << 1] = min(minn[id << 1], minn[id]);
st[id << 1] = max(st[id << 1], maxn[id << 1] - minn[id << 1]);
minn[id << 1 | 1] = min(minn[id << 1 | 1], minn[id]);
st[id << 1 | 1] = max(st[id << 1 | 1], maxn[id << 1 | 1] - minn[id << 1 | 1]);
minn[id] = Inf;
}
}
void UpdateHigh(int id, int l, int r, const int &x, const int &v)
{
if (l > x || r < x)
return;
if (l == x && r == x)
{
st[id] = max(st[id], maxn[id] - minn[id]);
maxn[id] = v;
minn[id] = Inf;
return;
}
Push(id);
UpdateHigh(id << 1, l, (l + r) / 2, x, v);
UpdateHigh(id << 1 | 1, (l + r) / 2 + 1, r, x, v);
st[id] = max({st[id], st[id << 1], st[id << 1 | 1]});
maxn[id] = max(maxn[id << 1], maxn[id << 1 | 1]);
}
void UpdateHigh(int x, int v)
{
UpdateHigh(1, 1, n, x, v);
}
void UpdateLow(int id, int l, int r, const int &a, const int &b, const int &v)
{
if (l > b || r < a)
return;
if (l >= a && r <= b)
{
minn[id] = min(minn[id], v);
st[id] = max(st[id], maxn[id] - minn[id]);
return;
}
Push(id);
UpdateLow(id << 1, l, (l + r) / 2, a, b, v);
UpdateLow(id << 1 | 1, (l + r) / 2 + 1, r, a, b, v);
st[id] = max({st[id], st[id << 1], st[id << 1 | 1]});
}
void UpdateLow(int l, int r, int v)
{
UpdateLow(1, 1, n, l, r, v);
}
int Get(int id, int l, int r, const int &a, const int &b)
{
if (l > b || r < a)
return -Inf;
if (l >= a && r <= b)
return st[id];
Push(id);
return max(Get(id << 1, l, (l + r) / 2, a, b), Get(id << 1 | 1, (l + r) / 2 + 1, r, a, b));
}
int Get(int l, int r)
{
return Get(1, 1, n, l, r);
}
} f;
int n, q, l[N], r[N], x[N], y[N], a[N], ans[N];
vector<int> in[N], out[N], que[N];
void Read()
{
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> a[i] >> x[i] >> y[i];
cin >> q;
for (int i = 1; i <= q; ++i)
{
cin >> l[i] >> r[i];
ans[i] = -1;
}
}
void Cal()
{
for (int i = 1; i <= q; ++i)
que[l[i]].emplace_back(i);
f.Assign(n);
for (int i = n; i; --i)
{
for (auto j : in[i])
f.UpdateHigh(j, a[j]);
for (auto j : out[i])
f.UpdateHigh(j, -Inf);
in[i].clear();
out[i].clear();
if (i + x[i] <= n)
f.UpdateLow(i + x[i], min(n, i + y[i]), a[i]);
for (auto j : que[i])
ans[j] = max(ans[j], f.Get(i, r[j]));
que[i].clear();
if (i - x[i] > 0)
in[i - x[i]].emplace_back(i);
if (i - y[i] - 1 > 0)
out[i - y[i] - 1].emplace_back(i);
}
}
void Solve()
{
Cal();
reverse(a + 1, a + n + 1);
reverse(x + 1, x + n + 1);
reverse(y + 1, y + n + 1);
for (int i = 1; i <= q; ++i)
{
l[i] = n - l[i] + 1;
r[i] = n - r[i] + 1;
swap(l[i], r[i]);
}
Cal();
for (int i = 1; i <= q; ++i)
cout << ans[i] << "\n";
}
int32_t main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if (fopen("palesta.INP", "r"))
{
freopen("paletsa.inp", "r", stdin);
freopen("palesta.out", "w", stdout);
}
int t(1);
if (typetest)
cin >> t;
for (int _ = 1; _ <= t; ++_)
{
// cout << "Case #" << _ << ": ";
Read();
Solve();
}
// cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}
/*
*/
Compilation message
antennas.cpp: In function 'void read(T&)':
antennas.cpp:12:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
12 | register int c;
| ^
antennas.cpp: In function 'int32_t main()':
antennas.cpp:194:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
194 | freopen("paletsa.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:195:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
195 | freopen("palesta.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
23756 KB |
Output is correct |
2 |
Correct |
16 ms |
23860 KB |
Output is correct |
3 |
Correct |
16 ms |
23760 KB |
Output is correct |
4 |
Correct |
14 ms |
23764 KB |
Output is correct |
5 |
Correct |
14 ms |
23760 KB |
Output is correct |
6 |
Correct |
16 ms |
23868 KB |
Output is correct |
7 |
Correct |
14 ms |
23740 KB |
Output is correct |
8 |
Correct |
14 ms |
23872 KB |
Output is correct |
9 |
Correct |
15 ms |
23756 KB |
Output is correct |
10 |
Correct |
14 ms |
23884 KB |
Output is correct |
11 |
Correct |
15 ms |
23756 KB |
Output is correct |
12 |
Correct |
15 ms |
23828 KB |
Output is correct |
13 |
Correct |
14 ms |
23756 KB |
Output is correct |
14 |
Correct |
14 ms |
23848 KB |
Output is correct |
15 |
Correct |
14 ms |
23764 KB |
Output is correct |
16 |
Correct |
15 ms |
23860 KB |
Output is correct |
17 |
Correct |
14 ms |
23760 KB |
Output is correct |
18 |
Correct |
14 ms |
23764 KB |
Output is correct |
19 |
Correct |
15 ms |
23760 KB |
Output is correct |
20 |
Correct |
16 ms |
23768 KB |
Output is correct |
21 |
Correct |
13 ms |
23756 KB |
Output is correct |
22 |
Correct |
17 ms |
23756 KB |
Output is correct |
23 |
Correct |
16 ms |
23764 KB |
Output is correct |
24 |
Correct |
14 ms |
23856 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
23756 KB |
Output is correct |
2 |
Correct |
16 ms |
23860 KB |
Output is correct |
3 |
Correct |
16 ms |
23760 KB |
Output is correct |
4 |
Correct |
14 ms |
23764 KB |
Output is correct |
5 |
Correct |
14 ms |
23760 KB |
Output is correct |
6 |
Correct |
16 ms |
23868 KB |
Output is correct |
7 |
Correct |
14 ms |
23740 KB |
Output is correct |
8 |
Correct |
14 ms |
23872 KB |
Output is correct |
9 |
Correct |
15 ms |
23756 KB |
Output is correct |
10 |
Correct |
14 ms |
23884 KB |
Output is correct |
11 |
Correct |
15 ms |
23756 KB |
Output is correct |
12 |
Correct |
15 ms |
23828 KB |
Output is correct |
13 |
Correct |
14 ms |
23756 KB |
Output is correct |
14 |
Correct |
14 ms |
23848 KB |
Output is correct |
15 |
Correct |
14 ms |
23764 KB |
Output is correct |
16 |
Correct |
15 ms |
23860 KB |
Output is correct |
17 |
Correct |
14 ms |
23760 KB |
Output is correct |
18 |
Correct |
14 ms |
23764 KB |
Output is correct |
19 |
Correct |
15 ms |
23760 KB |
Output is correct |
20 |
Correct |
16 ms |
23768 KB |
Output is correct |
21 |
Correct |
13 ms |
23756 KB |
Output is correct |
22 |
Correct |
17 ms |
23756 KB |
Output is correct |
23 |
Correct |
16 ms |
23764 KB |
Output is correct |
24 |
Correct |
14 ms |
23856 KB |
Output is correct |
25 |
Correct |
95 ms |
29320 KB |
Output is correct |
26 |
Correct |
24 ms |
24500 KB |
Output is correct |
27 |
Correct |
132 ms |
31468 KB |
Output is correct |
28 |
Correct |
124 ms |
31488 KB |
Output is correct |
29 |
Correct |
89 ms |
29404 KB |
Output is correct |
30 |
Correct |
87 ms |
28968 KB |
Output is correct |
31 |
Correct |
105 ms |
30824 KB |
Output is correct |
32 |
Correct |
123 ms |
31556 KB |
Output is correct |
33 |
Correct |
111 ms |
31144 KB |
Output is correct |
34 |
Correct |
69 ms |
27552 KB |
Output is correct |
35 |
Correct |
118 ms |
31636 KB |
Output is correct |
36 |
Correct |
125 ms |
31468 KB |
Output is correct |
37 |
Correct |
74 ms |
27716 KB |
Output is correct |
38 |
Correct |
123 ms |
30608 KB |
Output is correct |
39 |
Correct |
29 ms |
24812 KB |
Output is correct |
40 |
Correct |
116 ms |
30552 KB |
Output is correct |
41 |
Correct |
89 ms |
28824 KB |
Output is correct |
42 |
Correct |
117 ms |
30528 KB |
Output is correct |
43 |
Correct |
55 ms |
26172 KB |
Output is correct |
44 |
Correct |
117 ms |
30564 KB |
Output is correct |
45 |
Correct |
33 ms |
25060 KB |
Output is correct |
46 |
Correct |
119 ms |
30460 KB |
Output is correct |
47 |
Correct |
40 ms |
25540 KB |
Output is correct |
48 |
Correct |
119 ms |
30588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
307 ms |
34992 KB |
Output is correct |
2 |
Correct |
322 ms |
36228 KB |
Output is correct |
3 |
Correct |
217 ms |
32452 KB |
Output is correct |
4 |
Correct |
319 ms |
36164 KB |
Output is correct |
5 |
Correct |
133 ms |
29380 KB |
Output is correct |
6 |
Correct |
337 ms |
36208 KB |
Output is correct |
7 |
Correct |
269 ms |
34568 KB |
Output is correct |
8 |
Correct |
340 ms |
36272 KB |
Output is correct |
9 |
Correct |
47 ms |
25668 KB |
Output is correct |
10 |
Correct |
330 ms |
36176 KB |
Output is correct |
11 |
Correct |
202 ms |
31552 KB |
Output is correct |
12 |
Correct |
318 ms |
36216 KB |
Output is correct |
13 |
Correct |
208 ms |
33988 KB |
Output is correct |
14 |
Correct |
196 ms |
33684 KB |
Output is correct |
15 |
Correct |
214 ms |
32920 KB |
Output is correct |
16 |
Correct |
173 ms |
32968 KB |
Output is correct |
17 |
Correct |
219 ms |
34440 KB |
Output is correct |
18 |
Correct |
206 ms |
33344 KB |
Output is correct |
19 |
Correct |
199 ms |
33420 KB |
Output is correct |
20 |
Correct |
195 ms |
33636 KB |
Output is correct |
21 |
Correct |
188 ms |
34116 KB |
Output is correct |
22 |
Correct |
216 ms |
33676 KB |
Output is correct |
23 |
Correct |
197 ms |
33620 KB |
Output is correct |
24 |
Correct |
172 ms |
32576 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
23756 KB |
Output is correct |
2 |
Correct |
16 ms |
23860 KB |
Output is correct |
3 |
Correct |
16 ms |
23760 KB |
Output is correct |
4 |
Correct |
14 ms |
23764 KB |
Output is correct |
5 |
Correct |
14 ms |
23760 KB |
Output is correct |
6 |
Correct |
16 ms |
23868 KB |
Output is correct |
7 |
Correct |
14 ms |
23740 KB |
Output is correct |
8 |
Correct |
14 ms |
23872 KB |
Output is correct |
9 |
Correct |
15 ms |
23756 KB |
Output is correct |
10 |
Correct |
14 ms |
23884 KB |
Output is correct |
11 |
Correct |
15 ms |
23756 KB |
Output is correct |
12 |
Correct |
15 ms |
23828 KB |
Output is correct |
13 |
Correct |
14 ms |
23756 KB |
Output is correct |
14 |
Correct |
14 ms |
23848 KB |
Output is correct |
15 |
Correct |
14 ms |
23764 KB |
Output is correct |
16 |
Correct |
15 ms |
23860 KB |
Output is correct |
17 |
Correct |
14 ms |
23760 KB |
Output is correct |
18 |
Correct |
14 ms |
23764 KB |
Output is correct |
19 |
Correct |
15 ms |
23760 KB |
Output is correct |
20 |
Correct |
16 ms |
23768 KB |
Output is correct |
21 |
Correct |
13 ms |
23756 KB |
Output is correct |
22 |
Correct |
17 ms |
23756 KB |
Output is correct |
23 |
Correct |
16 ms |
23764 KB |
Output is correct |
24 |
Correct |
14 ms |
23856 KB |
Output is correct |
25 |
Correct |
95 ms |
29320 KB |
Output is correct |
26 |
Correct |
24 ms |
24500 KB |
Output is correct |
27 |
Correct |
132 ms |
31468 KB |
Output is correct |
28 |
Correct |
124 ms |
31488 KB |
Output is correct |
29 |
Correct |
89 ms |
29404 KB |
Output is correct |
30 |
Correct |
87 ms |
28968 KB |
Output is correct |
31 |
Correct |
105 ms |
30824 KB |
Output is correct |
32 |
Correct |
123 ms |
31556 KB |
Output is correct |
33 |
Correct |
111 ms |
31144 KB |
Output is correct |
34 |
Correct |
69 ms |
27552 KB |
Output is correct |
35 |
Correct |
118 ms |
31636 KB |
Output is correct |
36 |
Correct |
125 ms |
31468 KB |
Output is correct |
37 |
Correct |
74 ms |
27716 KB |
Output is correct |
38 |
Correct |
123 ms |
30608 KB |
Output is correct |
39 |
Correct |
29 ms |
24812 KB |
Output is correct |
40 |
Correct |
116 ms |
30552 KB |
Output is correct |
41 |
Correct |
89 ms |
28824 KB |
Output is correct |
42 |
Correct |
117 ms |
30528 KB |
Output is correct |
43 |
Correct |
55 ms |
26172 KB |
Output is correct |
44 |
Correct |
117 ms |
30564 KB |
Output is correct |
45 |
Correct |
33 ms |
25060 KB |
Output is correct |
46 |
Correct |
119 ms |
30460 KB |
Output is correct |
47 |
Correct |
40 ms |
25540 KB |
Output is correct |
48 |
Correct |
119 ms |
30588 KB |
Output is correct |
49 |
Correct |
307 ms |
34992 KB |
Output is correct |
50 |
Correct |
322 ms |
36228 KB |
Output is correct |
51 |
Correct |
217 ms |
32452 KB |
Output is correct |
52 |
Correct |
319 ms |
36164 KB |
Output is correct |
53 |
Correct |
133 ms |
29380 KB |
Output is correct |
54 |
Correct |
337 ms |
36208 KB |
Output is correct |
55 |
Correct |
269 ms |
34568 KB |
Output is correct |
56 |
Correct |
340 ms |
36272 KB |
Output is correct |
57 |
Correct |
47 ms |
25668 KB |
Output is correct |
58 |
Correct |
330 ms |
36176 KB |
Output is correct |
59 |
Correct |
202 ms |
31552 KB |
Output is correct |
60 |
Correct |
318 ms |
36216 KB |
Output is correct |
61 |
Correct |
208 ms |
33988 KB |
Output is correct |
62 |
Correct |
196 ms |
33684 KB |
Output is correct |
63 |
Correct |
214 ms |
32920 KB |
Output is correct |
64 |
Correct |
173 ms |
32968 KB |
Output is correct |
65 |
Correct |
219 ms |
34440 KB |
Output is correct |
66 |
Correct |
206 ms |
33344 KB |
Output is correct |
67 |
Correct |
199 ms |
33420 KB |
Output is correct |
68 |
Correct |
195 ms |
33636 KB |
Output is correct |
69 |
Correct |
188 ms |
34116 KB |
Output is correct |
70 |
Correct |
216 ms |
33676 KB |
Output is correct |
71 |
Correct |
197 ms |
33620 KB |
Output is correct |
72 |
Correct |
172 ms |
32576 KB |
Output is correct |
73 |
Correct |
496 ms |
44376 KB |
Output is correct |
74 |
Correct |
370 ms |
37620 KB |
Output is correct |
75 |
Correct |
470 ms |
43384 KB |
Output is correct |
76 |
Correct |
649 ms |
48336 KB |
Output is correct |
77 |
Correct |
307 ms |
37172 KB |
Output is correct |
78 |
Correct |
582 ms |
45184 KB |
Output is correct |
79 |
Correct |
590 ms |
46240 KB |
Output is correct |
80 |
Correct |
634 ms |
48324 KB |
Output is correct |
81 |
Correct |
215 ms |
34088 KB |
Output is correct |
82 |
Correct |
484 ms |
43244 KB |
Output is correct |
83 |
Correct |
426 ms |
42188 KB |
Output is correct |
84 |
Correct |
616 ms |
48324 KB |
Output is correct |
85 |
Correct |
413 ms |
41356 KB |
Output is correct |
86 |
Correct |
499 ms |
44656 KB |
Output is correct |
87 |
Correct |
231 ms |
35100 KB |
Output is correct |
88 |
Correct |
420 ms |
43996 KB |
Output is correct |
89 |
Correct |
476 ms |
43300 KB |
Output is correct |
90 |
Correct |
478 ms |
44356 KB |
Output is correct |
91 |
Correct |
295 ms |
38192 KB |
Output is correct |
92 |
Correct |
477 ms |
44812 KB |
Output is correct |
93 |
Correct |
252 ms |
36540 KB |
Output is correct |
94 |
Correct |
457 ms |
44656 KB |
Output is correct |
95 |
Correct |
337 ms |
37400 KB |
Output is correct |
96 |
Correct |
442 ms |
43624 KB |
Output is correct |