#include <bits/stdc++.h>
using namespace std;
const int INF = 2e9;
struct antenna{
int l, r, h;
};
antenna a[200005];
struct complaint{
int l, r, p;
bool operator < (const complaint &aux)const{
if(r != aux.r) return r < aux.r;
return l < aux.l;
}
};
complaint x[200005];
int n, q;
int ans[200005];
set <pair <int, int> > s;
set <pair <int, int> > s2;
int Min[800005], Max[800005], hMax[800005], hMin[800005], Sol[800005], LazyMin[800005], LazyMax[800005];
void build(int st = 1, int dr = n, int nod = 1){
if(st == dr){
Min[nod] = INF; Max[nod] = 0;
hMin[nod] = INF; hMax[nod] = 0;
Sol[nod] = -1;
return ;
}
int mij = (st + dr) / 2;
build(st, mij, nod * 2);
build(mij + 1, dr, nod * 2 + 1);
Min[nod] = min(Min[nod * 2], Min[nod * 2 + 1]);
Max[nod] = max(Max[nod * 2], Max[nod * 2 + 1]);
hMin[nod] = min(hMin[nod * 2], hMin[nod * 2 + 1]);
hMax[nod] = max(hMax[nod * 2], hMax[nod * 2 + 1]);
Sol[nod] = -1; LazyMin[nod] = INF;
}
void propag(int nod){
if(LazyMin[nod] != INF){
Min[2 * nod] = min(Min[2 * nod], LazyMin[nod]);
Min[2 * nod + 1] = min(Min[2 * nod + 1], LazyMin[nod]);
LazyMin[nod * 2] = min(LazyMin[nod], LazyMin[nod * 2]);
LazyMin[nod * 2 + 1] = min(LazyMin[nod], LazyMin[nod * 2 + 1]);
}
if(LazyMax[nod] != 0){
Max[2 * nod] = max(Max[2 * nod], LazyMax[nod]);
Max[2 * nod + 1] = max(Max[2 * nod + 1], LazyMax[nod]);
LazyMax[nod * 2] = max(LazyMax[nod], LazyMax[nod * 2]);
LazyMax[nod * 2 + 1] = max(LazyMax[nod], LazyMax[nod * 2 + 1]);
}
Sol[2 * nod] = max(Sol[2 * nod], max(hMax[2 * nod] - LazyMin[nod], LazyMax[nod] - hMin[2 * nod]));
Sol[2 * nod + 1] = max(Sol[2 * nod + 1], max(hMax[2 * nod + 1] - LazyMin[nod], LazyMax[nod] - hMin[2 * nod + 1]));
LazyMin[nod] = INF; LazyMax[nod] = 0;
}
void update(int x, int y, int v, int st = 1, int dr = n, int nod = 1){
if(st != dr) propag(nod);
if(hMin[nod] == INF) return ;
if(x <= st && dr <= y){
LazyMax[nod] = max(LazyMax[nod], v);
LazyMin[nod] = min(LazyMin[nod], v);
Min[nod] = min(Min[nod], v);
Max[nod] = max(Max[nod], v);
Sol[nod] = max(Sol[nod], max(hMax[nod] - v, v - hMin[nod]));
return ;
}
int mij = (st + dr) / 2;
if(x <= mij) update(x, y, v, st, mij, nod * 2);
if(mij + 1 <= y) update(x, y, v, mij + 1, dr, nod * 2 + 1);
Min[nod] = min(Min[nod * 2], Min[nod * 2 + 1]);
Max[nod] = max(Max[nod * 2], Max[nod * 2 + 1]);
hMin[nod] = min(hMin[nod * 2], hMin[nod * 2 + 1]);
hMax[nod] = max(hMax[nod * 2], hMax[nod * 2 + 1]);
Sol[nod] = max(Sol[nod * 2], Sol[nod * 2 + 1]);
}
void update2(int x, int v, int st = 1, int dr = n, int nod = 1){
if(st != dr) propag(nod);
if(st == dr){
if(v == -2) hMin[nod] = a[st].h, hMax[nod] = a[st].h;
else hMin[nod] = INF, hMax[nod] = 0;
return ;
}
int mij = (st + dr) / 2;
if(x <= mij) update2(x, v, st, mij, nod * 2);
else update2(x, v, mij + 1, dr, nod * 2 + 1);
Min[nod] = min(Min[nod * 2], Min[nod * 2 + 1]);
Max[nod] = max(Max[nod * 2], Max[nod * 2 + 1]);
hMin[nod] = min(hMin[nod * 2], hMin[nod * 2 + 1]);
hMax[nod] = max(hMax[nod * 2], hMax[nod * 2 + 1]);
Sol[nod] = max(Sol[nod * 2], Sol[nod * 2 + 1]);
}
int query(int x, int y, int st = 1, int dr = n, int nod = 1){
if(x <= st) return Sol[nod];
if(st != dr) propag(nod);
int mij = (st + dr) / 2, a1 = -1, a2 = -1;
if(x <= mij) a1 = query(x, y, st, mij, nod * 2);
if(mij + 1 <= y) a2 = query(x, y, mij + 1, dr, nod * 2 + 1);
return max(a1, a2);
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n ; ++i)
scanf("%d%d%d", &a[i].h, &a[i].l, &a[i].r);
scanf("%d", &q);
for(int i = 1; i <= q ; ++i) scanf("%d%d", &x[i].l, &x[i].r), x[i].p = i;
sort(x + 1, x + q + 1);
build();
int j = 1;
for(int i = 1; i <= q ; ++i){
while(j <= n && j <= x[i].r){
while(!s2.empty() && s2.begin()->first < j){
update2(s2.begin()->second, -2);
s.insert({a[s2.begin()->second].r + s2.begin()->second, s2.begin()->second});
s2.erase(s2.begin());
}
while(!s.empty() && s.begin()->first < j){
update2(s.begin()->second, -1);
s.erase(s.begin());
}
if(j - a[j].l >= 1) update(max(1, j - a[j].r), j - a[j].l, a[j].h);
if(a[j].l != 1 && j + a[j].l - 1 <= n) s2.insert({j + a[j].l - 1, j});
else if(j + a[j].l - 1 <= n){
update2(j, -2);
if(j + a[j].r <= n) s.insert({j + a[j].r, j});
}
++j;
}
ans[x[i].p] = query(x[i].l, x[i].r);
}
for(int i = 1; i <= q ; ++i) printf("%d\n", ans[i]);
return 0;
}
Compilation message
antennas.cpp: In function 'int main()':
antennas.cpp:133:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
antennas.cpp:135:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &a[i].h, &a[i].l, &a[i].r);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:137:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
~~~~~^~~~~~~~~~
antennas.cpp:138:65: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i = 1; i <= q ; ++i) scanf("%d%d", &x[i].l, &x[i].r), x[i].p = i;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
504 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
3 ms |
632 KB |
Output is correct |
5 |
Correct |
3 ms |
376 KB |
Output is correct |
6 |
Correct |
3 ms |
376 KB |
Output is correct |
7 |
Correct |
3 ms |
504 KB |
Output is correct |
8 |
Correct |
3 ms |
504 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
3 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
3 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
504 KB |
Output is correct |
14 |
Correct |
2 ms |
504 KB |
Output is correct |
15 |
Correct |
3 ms |
504 KB |
Output is correct |
16 |
Correct |
2 ms |
504 KB |
Output is correct |
17 |
Correct |
3 ms |
504 KB |
Output is correct |
18 |
Correct |
2 ms |
504 KB |
Output is correct |
19 |
Correct |
2 ms |
376 KB |
Output is correct |
20 |
Correct |
3 ms |
376 KB |
Output is correct |
21 |
Correct |
3 ms |
376 KB |
Output is correct |
22 |
Correct |
3 ms |
504 KB |
Output is correct |
23 |
Correct |
3 ms |
376 KB |
Output is correct |
24 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
504 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
3 ms |
632 KB |
Output is correct |
5 |
Correct |
3 ms |
376 KB |
Output is correct |
6 |
Correct |
3 ms |
376 KB |
Output is correct |
7 |
Correct |
3 ms |
504 KB |
Output is correct |
8 |
Correct |
3 ms |
504 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
3 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
3 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
504 KB |
Output is correct |
14 |
Correct |
2 ms |
504 KB |
Output is correct |
15 |
Correct |
3 ms |
504 KB |
Output is correct |
16 |
Correct |
2 ms |
504 KB |
Output is correct |
17 |
Correct |
3 ms |
504 KB |
Output is correct |
18 |
Correct |
2 ms |
504 KB |
Output is correct |
19 |
Correct |
2 ms |
376 KB |
Output is correct |
20 |
Correct |
3 ms |
376 KB |
Output is correct |
21 |
Correct |
3 ms |
376 KB |
Output is correct |
22 |
Correct |
3 ms |
504 KB |
Output is correct |
23 |
Correct |
3 ms |
376 KB |
Output is correct |
24 |
Correct |
2 ms |
376 KB |
Output is correct |
25 |
Correct |
91 ms |
5240 KB |
Output is correct |
26 |
Correct |
14 ms |
1144 KB |
Output is correct |
27 |
Correct |
132 ms |
7260 KB |
Output is correct |
28 |
Correct |
149 ms |
7416 KB |
Output is correct |
29 |
Correct |
92 ms |
5240 KB |
Output is correct |
30 |
Correct |
91 ms |
5112 KB |
Output is correct |
31 |
Correct |
109 ms |
6492 KB |
Output is correct |
32 |
Correct |
134 ms |
7416 KB |
Output is correct |
33 |
Correct |
121 ms |
6904 KB |
Output is correct |
34 |
Correct |
67 ms |
3832 KB |
Output is correct |
35 |
Correct |
129 ms |
7164 KB |
Output is correct |
36 |
Correct |
133 ms |
7288 KB |
Output is correct |
37 |
Correct |
75 ms |
3848 KB |
Output is correct |
38 |
Correct |
130 ms |
6300 KB |
Output is correct |
39 |
Correct |
21 ms |
1400 KB |
Output is correct |
40 |
Correct |
129 ms |
6392 KB |
Output is correct |
41 |
Correct |
93 ms |
4856 KB |
Output is correct |
42 |
Correct |
129 ms |
6264 KB |
Output is correct |
43 |
Correct |
45 ms |
2556 KB |
Output is correct |
44 |
Correct |
129 ms |
6284 KB |
Output is correct |
45 |
Correct |
25 ms |
1656 KB |
Output is correct |
46 |
Correct |
129 ms |
6264 KB |
Output is correct |
47 |
Correct |
35 ms |
2040 KB |
Output is correct |
48 |
Correct |
128 ms |
6264 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
479 ms |
20132 KB |
Output is correct |
2 |
Correct |
557 ms |
25332 KB |
Output is correct |
3 |
Correct |
358 ms |
22136 KB |
Output is correct |
4 |
Correct |
552 ms |
25212 KB |
Output is correct |
5 |
Correct |
204 ms |
12416 KB |
Output is correct |
6 |
Correct |
530 ms |
25212 KB |
Output is correct |
7 |
Correct |
446 ms |
23928 KB |
Output is correct |
8 |
Correct |
540 ms |
25208 KB |
Output is correct |
9 |
Correct |
54 ms |
3960 KB |
Output is correct |
10 |
Correct |
520 ms |
25272 KB |
Output is correct |
11 |
Correct |
285 ms |
14200 KB |
Output is correct |
12 |
Correct |
545 ms |
25208 KB |
Output is correct |
13 |
Correct |
273 ms |
24824 KB |
Output is correct |
14 |
Correct |
248 ms |
24568 KB |
Output is correct |
15 |
Correct |
259 ms |
24696 KB |
Output is correct |
16 |
Correct |
247 ms |
24952 KB |
Output is correct |
17 |
Correct |
285 ms |
25208 KB |
Output is correct |
18 |
Correct |
257 ms |
24824 KB |
Output is correct |
19 |
Correct |
271 ms |
24812 KB |
Output is correct |
20 |
Correct |
266 ms |
24824 KB |
Output is correct |
21 |
Correct |
250 ms |
24440 KB |
Output is correct |
22 |
Correct |
258 ms |
24696 KB |
Output is correct |
23 |
Correct |
260 ms |
24576 KB |
Output is correct |
24 |
Correct |
245 ms |
24700 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
504 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
3 ms |
632 KB |
Output is correct |
5 |
Correct |
3 ms |
376 KB |
Output is correct |
6 |
Correct |
3 ms |
376 KB |
Output is correct |
7 |
Correct |
3 ms |
504 KB |
Output is correct |
8 |
Correct |
3 ms |
504 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
3 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
3 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
504 KB |
Output is correct |
14 |
Correct |
2 ms |
504 KB |
Output is correct |
15 |
Correct |
3 ms |
504 KB |
Output is correct |
16 |
Correct |
2 ms |
504 KB |
Output is correct |
17 |
Correct |
3 ms |
504 KB |
Output is correct |
18 |
Correct |
2 ms |
504 KB |
Output is correct |
19 |
Correct |
2 ms |
376 KB |
Output is correct |
20 |
Correct |
3 ms |
376 KB |
Output is correct |
21 |
Correct |
3 ms |
376 KB |
Output is correct |
22 |
Correct |
3 ms |
504 KB |
Output is correct |
23 |
Correct |
3 ms |
376 KB |
Output is correct |
24 |
Correct |
2 ms |
376 KB |
Output is correct |
25 |
Correct |
91 ms |
5240 KB |
Output is correct |
26 |
Correct |
14 ms |
1144 KB |
Output is correct |
27 |
Correct |
132 ms |
7260 KB |
Output is correct |
28 |
Correct |
149 ms |
7416 KB |
Output is correct |
29 |
Correct |
92 ms |
5240 KB |
Output is correct |
30 |
Correct |
91 ms |
5112 KB |
Output is correct |
31 |
Correct |
109 ms |
6492 KB |
Output is correct |
32 |
Correct |
134 ms |
7416 KB |
Output is correct |
33 |
Correct |
121 ms |
6904 KB |
Output is correct |
34 |
Correct |
67 ms |
3832 KB |
Output is correct |
35 |
Correct |
129 ms |
7164 KB |
Output is correct |
36 |
Correct |
133 ms |
7288 KB |
Output is correct |
37 |
Correct |
75 ms |
3848 KB |
Output is correct |
38 |
Correct |
130 ms |
6300 KB |
Output is correct |
39 |
Correct |
21 ms |
1400 KB |
Output is correct |
40 |
Correct |
129 ms |
6392 KB |
Output is correct |
41 |
Correct |
93 ms |
4856 KB |
Output is correct |
42 |
Correct |
129 ms |
6264 KB |
Output is correct |
43 |
Correct |
45 ms |
2556 KB |
Output is correct |
44 |
Correct |
129 ms |
6284 KB |
Output is correct |
45 |
Correct |
25 ms |
1656 KB |
Output is correct |
46 |
Correct |
129 ms |
6264 KB |
Output is correct |
47 |
Correct |
35 ms |
2040 KB |
Output is correct |
48 |
Correct |
128 ms |
6264 KB |
Output is correct |
49 |
Correct |
479 ms |
20132 KB |
Output is correct |
50 |
Correct |
557 ms |
25332 KB |
Output is correct |
51 |
Correct |
358 ms |
22136 KB |
Output is correct |
52 |
Correct |
552 ms |
25212 KB |
Output is correct |
53 |
Correct |
204 ms |
12416 KB |
Output is correct |
54 |
Correct |
530 ms |
25212 KB |
Output is correct |
55 |
Correct |
446 ms |
23928 KB |
Output is correct |
56 |
Correct |
540 ms |
25208 KB |
Output is correct |
57 |
Correct |
54 ms |
3960 KB |
Output is correct |
58 |
Correct |
520 ms |
25272 KB |
Output is correct |
59 |
Correct |
285 ms |
14200 KB |
Output is correct |
60 |
Correct |
545 ms |
25208 KB |
Output is correct |
61 |
Correct |
273 ms |
24824 KB |
Output is correct |
62 |
Correct |
248 ms |
24568 KB |
Output is correct |
63 |
Correct |
259 ms |
24696 KB |
Output is correct |
64 |
Correct |
247 ms |
24952 KB |
Output is correct |
65 |
Correct |
285 ms |
25208 KB |
Output is correct |
66 |
Correct |
257 ms |
24824 KB |
Output is correct |
67 |
Correct |
271 ms |
24812 KB |
Output is correct |
68 |
Correct |
266 ms |
24824 KB |
Output is correct |
69 |
Correct |
250 ms |
24440 KB |
Output is correct |
70 |
Correct |
258 ms |
24696 KB |
Output is correct |
71 |
Correct |
260 ms |
24576 KB |
Output is correct |
72 |
Correct |
245 ms |
24700 KB |
Output is correct |
73 |
Correct |
676 ms |
29908 KB |
Output is correct |
74 |
Correct |
562 ms |
25976 KB |
Output is correct |
75 |
Correct |
576 ms |
29604 KB |
Output is correct |
76 |
Correct |
772 ms |
33060 KB |
Output is correct |
77 |
Correct |
355 ms |
17912 KB |
Output is correct |
78 |
Correct |
704 ms |
30584 KB |
Output is correct |
79 |
Correct |
703 ms |
31480 KB |
Output is correct |
80 |
Correct |
800 ms |
32888 KB |
Output is correct |
81 |
Correct |
221 ms |
10872 KB |
Output is correct |
82 |
Correct |
660 ms |
29176 KB |
Output is correct |
83 |
Correct |
504 ms |
21624 KB |
Output is correct |
84 |
Correct |
770 ms |
33016 KB |
Output is correct |
85 |
Correct |
396 ms |
28920 KB |
Output is correct |
86 |
Correct |
452 ms |
31808 KB |
Output is correct |
87 |
Correct |
293 ms |
26232 KB |
Output is correct |
88 |
Correct |
467 ms |
31740 KB |
Output is correct |
89 |
Correct |
439 ms |
30364 KB |
Output is correct |
90 |
Correct |
542 ms |
31736 KB |
Output is correct |
91 |
Correct |
346 ms |
27420 KB |
Output is correct |
92 |
Correct |
471 ms |
31864 KB |
Output is correct |
93 |
Correct |
304 ms |
26244 KB |
Output is correct |
94 |
Correct |
458 ms |
31692 KB |
Output is correct |
95 |
Correct |
313 ms |
26888 KB |
Output is correct |
96 |
Correct |
512 ms |
31864 KB |
Output is correct |