#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
typedef pair<ll, ll> ii;
#define X first
#define Y second
#define pb push_back
#define MAXN 800200
#define INF 1001001001
int n, nn = 1 << 18;
int h[MAXN], a[MAXN], b[MAXN];
int q;
int _l[MAXN], _r[MAXN];
int reza[MAXN];
vector<ii> v[MAXN];
vector<int> ad[MAXN], rem[MAXN];
int c[MAXN], d[MAXN], pd[MAXN];
void propaj(int cv)
{
d[cv] = max(d[cv], c[cv] - pd[cv]);
if (cv < nn) {
pd[cv * 2] = min(pd[cv * 2], pd[cv]);
pd[cv * 2 + 1] = min(pd[cv * 2 + 1], pd[cv]);
}
pd[cv] = INF;
}
void setaj(int cv, int lo, int hi, int w, int e)
{
propaj(cv);
if (lo > hi || lo > w || hi < w) return;
if (lo == hi) {
c[cv] = e;
return;
}
int mid = (lo + hi) / 2;
setaj(cv * 2, lo, mid, w, e);
setaj(cv * 2 + 1, mid + 1, hi, w, e);
c[cv] = max(c[cv * 2], c[cv * 2 + 1]);
}
void upd(int cv, int lo, int hi, int l, int r, int w)
{
propaj(cv);
if (lo > hi || lo > r || hi < l) return;
if (lo >= l && hi <= r) {
pd[cv] = min(pd[cv], w);
propaj(cv);
return;
}
int mid = (lo + hi) / 2;
upd(cv * 2, lo, mid, l, r, w);
upd(cv * 2 + 1, mid + 1, hi, l, r, w);
d[cv] = max(d[cv * 2], d[cv * 2 + 1]);
}
int kveri(int cv, int lo, int hi, int l, int r)
{
propaj(cv);
if (lo > hi || lo > r || hi < l) return -1;
if (lo >= l && hi <= r) return d[cv];
int mid = (lo + hi) / 2;
return max(kveri(cv * 2, lo, mid, l, r), kveri(cv * 2 + 1, mid + 1, hi, l, r));
}
void solve()
{
for (int i = 0; i < q; i++) {
v[_r[i]].pb({_l[i], i});
}
for (int i = 0; i < n; i++) {
ad[i + a[i]].pb(i);
rem[i + b[i] + 1].pb(i);
}
for (int i = 0; i < n; i++) {
for (int j: ad[i]) {
setaj(1, 0, nn - 1, j, h[j]);//cout<<i<<'+'<<j<<endl;
}
for (int j: rem[i]) {
setaj(1, 0, nn - 1, j, -1);//cout<<i<<'-'<<j<<endl;
}
upd(1, 0, nn - 1, i - b[i], i - a[i], h[i]);//cout<<i-b[i]<<'.'<<i-a[i]<<'.'<<h[i]<<endl;
for (ii j: v[i]) {
reza[j.Y] = max(reza[j.Y], kveri(1, 0, nn - 1, j.X, i));
}
}
}
int main()
{
memset(reza, -1, sizeof reza);
memset(c, -1, sizeof c);
memset(d, -1, sizeof d);
for (int i = 0; i < MAXN; i++) pd[i] = INF;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d%d%d", &h[i], &a[i], &b[i]);
}
scanf("%d", &q);
for (int i = 0; i < q; i++) {
scanf("%d%d", &_l[i], &_r[i]);
_l[i]--; _r[i]--;
}
solve();
reverse(h, h + n);
reverse(a, a + n);
reverse(b, b + n);
for (int i = 0; i < q; i++) {
_l[i] = n - 1 - _l[i];
_r[i] = n - 1 - _r[i];
swap(_l[i], _r[i]);
}
for (int i = 0; i < n; i++) {
v[i].clear();
ad[i].clear();
rem[i].clear();
}
memset(c, -1, sizeof c);
memset(d, -1, sizeof d);
for (int i = 0; i < MAXN; i++) pd[i] = INF;
solve();
for (int i = 0; i < q; i++) {
printf("%d\n", reza[i]);
}
return 0;
}
Compilation message
antennas.cpp: In function 'int main()':
antennas.cpp:110:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
antennas.cpp:112:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &h[i], &a[i], &b[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:114:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
~~~~~^~~~~~~~~~
antennas.cpp:116:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &_l[i], &_r[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
46 ms |
69240 KB |
Output is correct |
2 |
Correct |
45 ms |
69248 KB |
Output is correct |
3 |
Correct |
47 ms |
69240 KB |
Output is correct |
4 |
Correct |
45 ms |
69276 KB |
Output is correct |
5 |
Correct |
45 ms |
69248 KB |
Output is correct |
6 |
Correct |
47 ms |
69376 KB |
Output is correct |
7 |
Correct |
46 ms |
69368 KB |
Output is correct |
8 |
Correct |
45 ms |
69340 KB |
Output is correct |
9 |
Correct |
45 ms |
69240 KB |
Output is correct |
10 |
Correct |
45 ms |
69240 KB |
Output is correct |
11 |
Correct |
46 ms |
69368 KB |
Output is correct |
12 |
Correct |
46 ms |
69240 KB |
Output is correct |
13 |
Correct |
45 ms |
69240 KB |
Output is correct |
14 |
Correct |
45 ms |
69240 KB |
Output is correct |
15 |
Correct |
45 ms |
69336 KB |
Output is correct |
16 |
Correct |
48 ms |
69240 KB |
Output is correct |
17 |
Correct |
47 ms |
69248 KB |
Output is correct |
18 |
Correct |
54 ms |
69400 KB |
Output is correct |
19 |
Correct |
46 ms |
69244 KB |
Output is correct |
20 |
Correct |
53 ms |
69240 KB |
Output is correct |
21 |
Correct |
46 ms |
69368 KB |
Output is correct |
22 |
Correct |
53 ms |
69240 KB |
Output is correct |
23 |
Correct |
46 ms |
69368 KB |
Output is correct |
24 |
Correct |
47 ms |
69348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
46 ms |
69240 KB |
Output is correct |
2 |
Correct |
45 ms |
69248 KB |
Output is correct |
3 |
Correct |
47 ms |
69240 KB |
Output is correct |
4 |
Correct |
45 ms |
69276 KB |
Output is correct |
5 |
Correct |
45 ms |
69248 KB |
Output is correct |
6 |
Correct |
47 ms |
69376 KB |
Output is correct |
7 |
Correct |
46 ms |
69368 KB |
Output is correct |
8 |
Correct |
45 ms |
69340 KB |
Output is correct |
9 |
Correct |
45 ms |
69240 KB |
Output is correct |
10 |
Correct |
45 ms |
69240 KB |
Output is correct |
11 |
Correct |
46 ms |
69368 KB |
Output is correct |
12 |
Correct |
46 ms |
69240 KB |
Output is correct |
13 |
Correct |
45 ms |
69240 KB |
Output is correct |
14 |
Correct |
45 ms |
69240 KB |
Output is correct |
15 |
Correct |
45 ms |
69336 KB |
Output is correct |
16 |
Correct |
48 ms |
69240 KB |
Output is correct |
17 |
Correct |
47 ms |
69248 KB |
Output is correct |
18 |
Correct |
54 ms |
69400 KB |
Output is correct |
19 |
Correct |
46 ms |
69244 KB |
Output is correct |
20 |
Correct |
53 ms |
69240 KB |
Output is correct |
21 |
Correct |
46 ms |
69368 KB |
Output is correct |
22 |
Correct |
53 ms |
69240 KB |
Output is correct |
23 |
Correct |
46 ms |
69368 KB |
Output is correct |
24 |
Correct |
47 ms |
69348 KB |
Output is correct |
25 |
Correct |
250 ms |
77816 KB |
Output is correct |
26 |
Correct |
73 ms |
70264 KB |
Output is correct |
27 |
Correct |
337 ms |
80888 KB |
Output is correct |
28 |
Correct |
338 ms |
80760 KB |
Output is correct |
29 |
Correct |
254 ms |
78072 KB |
Output is correct |
30 |
Correct |
242 ms |
77484 KB |
Output is correct |
31 |
Correct |
293 ms |
79736 KB |
Output is correct |
32 |
Correct |
362 ms |
80760 KB |
Output is correct |
33 |
Correct |
327 ms |
80632 KB |
Output is correct |
34 |
Correct |
201 ms |
74872 KB |
Output is correct |
35 |
Correct |
350 ms |
81528 KB |
Output is correct |
36 |
Correct |
356 ms |
80760 KB |
Output is correct |
37 |
Correct |
208 ms |
75512 KB |
Output is correct |
38 |
Correct |
332 ms |
79740 KB |
Output is correct |
39 |
Correct |
88 ms |
70904 KB |
Output is correct |
40 |
Correct |
345 ms |
79744 KB |
Output is correct |
41 |
Correct |
255 ms |
77560 KB |
Output is correct |
42 |
Correct |
336 ms |
79736 KB |
Output is correct |
43 |
Correct |
141 ms |
72952 KB |
Output is correct |
44 |
Correct |
340 ms |
79736 KB |
Output is correct |
45 |
Correct |
96 ms |
71288 KB |
Output is correct |
46 |
Correct |
328 ms |
79736 KB |
Output is correct |
47 |
Correct |
120 ms |
72056 KB |
Output is correct |
48 |
Correct |
342 ms |
79608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
604 ms |
87932 KB |
Output is correct |
2 |
Correct |
734 ms |
89972 KB |
Output is correct |
3 |
Correct |
490 ms |
83704 KB |
Output is correct |
4 |
Correct |
739 ms |
90232 KB |
Output is correct |
5 |
Correct |
308 ms |
78712 KB |
Output is correct |
6 |
Correct |
689 ms |
90104 KB |
Output is correct |
7 |
Correct |
566 ms |
87180 KB |
Output is correct |
8 |
Correct |
685 ms |
90104 KB |
Output is correct |
9 |
Correct |
118 ms |
72440 KB |
Output is correct |
10 |
Correct |
713 ms |
89976 KB |
Output is correct |
11 |
Correct |
412 ms |
82168 KB |
Output is correct |
12 |
Correct |
677 ms |
89976 KB |
Output is correct |
13 |
Correct |
486 ms |
85452 KB |
Output is correct |
14 |
Correct |
446 ms |
84852 KB |
Output is correct |
15 |
Correct |
459 ms |
84544 KB |
Output is correct |
16 |
Correct |
436 ms |
85488 KB |
Output is correct |
17 |
Correct |
528 ms |
85792 KB |
Output is correct |
18 |
Correct |
469 ms |
84588 KB |
Output is correct |
19 |
Correct |
503 ms |
84688 KB |
Output is correct |
20 |
Correct |
463 ms |
85056 KB |
Output is correct |
21 |
Correct |
449 ms |
85976 KB |
Output is correct |
22 |
Correct |
484 ms |
85008 KB |
Output is correct |
23 |
Correct |
489 ms |
85088 KB |
Output is correct |
24 |
Correct |
432 ms |
84596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
46 ms |
69240 KB |
Output is correct |
2 |
Correct |
45 ms |
69248 KB |
Output is correct |
3 |
Correct |
47 ms |
69240 KB |
Output is correct |
4 |
Correct |
45 ms |
69276 KB |
Output is correct |
5 |
Correct |
45 ms |
69248 KB |
Output is correct |
6 |
Correct |
47 ms |
69376 KB |
Output is correct |
7 |
Correct |
46 ms |
69368 KB |
Output is correct |
8 |
Correct |
45 ms |
69340 KB |
Output is correct |
9 |
Correct |
45 ms |
69240 KB |
Output is correct |
10 |
Correct |
45 ms |
69240 KB |
Output is correct |
11 |
Correct |
46 ms |
69368 KB |
Output is correct |
12 |
Correct |
46 ms |
69240 KB |
Output is correct |
13 |
Correct |
45 ms |
69240 KB |
Output is correct |
14 |
Correct |
45 ms |
69240 KB |
Output is correct |
15 |
Correct |
45 ms |
69336 KB |
Output is correct |
16 |
Correct |
48 ms |
69240 KB |
Output is correct |
17 |
Correct |
47 ms |
69248 KB |
Output is correct |
18 |
Correct |
54 ms |
69400 KB |
Output is correct |
19 |
Correct |
46 ms |
69244 KB |
Output is correct |
20 |
Correct |
53 ms |
69240 KB |
Output is correct |
21 |
Correct |
46 ms |
69368 KB |
Output is correct |
22 |
Correct |
53 ms |
69240 KB |
Output is correct |
23 |
Correct |
46 ms |
69368 KB |
Output is correct |
24 |
Correct |
47 ms |
69348 KB |
Output is correct |
25 |
Correct |
250 ms |
77816 KB |
Output is correct |
26 |
Correct |
73 ms |
70264 KB |
Output is correct |
27 |
Correct |
337 ms |
80888 KB |
Output is correct |
28 |
Correct |
338 ms |
80760 KB |
Output is correct |
29 |
Correct |
254 ms |
78072 KB |
Output is correct |
30 |
Correct |
242 ms |
77484 KB |
Output is correct |
31 |
Correct |
293 ms |
79736 KB |
Output is correct |
32 |
Correct |
362 ms |
80760 KB |
Output is correct |
33 |
Correct |
327 ms |
80632 KB |
Output is correct |
34 |
Correct |
201 ms |
74872 KB |
Output is correct |
35 |
Correct |
350 ms |
81528 KB |
Output is correct |
36 |
Correct |
356 ms |
80760 KB |
Output is correct |
37 |
Correct |
208 ms |
75512 KB |
Output is correct |
38 |
Correct |
332 ms |
79740 KB |
Output is correct |
39 |
Correct |
88 ms |
70904 KB |
Output is correct |
40 |
Correct |
345 ms |
79744 KB |
Output is correct |
41 |
Correct |
255 ms |
77560 KB |
Output is correct |
42 |
Correct |
336 ms |
79736 KB |
Output is correct |
43 |
Correct |
141 ms |
72952 KB |
Output is correct |
44 |
Correct |
340 ms |
79736 KB |
Output is correct |
45 |
Correct |
96 ms |
71288 KB |
Output is correct |
46 |
Correct |
328 ms |
79736 KB |
Output is correct |
47 |
Correct |
120 ms |
72056 KB |
Output is correct |
48 |
Correct |
342 ms |
79608 KB |
Output is correct |
49 |
Correct |
604 ms |
87932 KB |
Output is correct |
50 |
Correct |
734 ms |
89972 KB |
Output is correct |
51 |
Correct |
490 ms |
83704 KB |
Output is correct |
52 |
Correct |
739 ms |
90232 KB |
Output is correct |
53 |
Correct |
308 ms |
78712 KB |
Output is correct |
54 |
Correct |
689 ms |
90104 KB |
Output is correct |
55 |
Correct |
566 ms |
87180 KB |
Output is correct |
56 |
Correct |
685 ms |
90104 KB |
Output is correct |
57 |
Correct |
118 ms |
72440 KB |
Output is correct |
58 |
Correct |
713 ms |
89976 KB |
Output is correct |
59 |
Correct |
412 ms |
82168 KB |
Output is correct |
60 |
Correct |
677 ms |
89976 KB |
Output is correct |
61 |
Correct |
486 ms |
85452 KB |
Output is correct |
62 |
Correct |
446 ms |
84852 KB |
Output is correct |
63 |
Correct |
459 ms |
84544 KB |
Output is correct |
64 |
Correct |
436 ms |
85488 KB |
Output is correct |
65 |
Correct |
528 ms |
85792 KB |
Output is correct |
66 |
Correct |
469 ms |
84588 KB |
Output is correct |
67 |
Correct |
503 ms |
84688 KB |
Output is correct |
68 |
Correct |
463 ms |
85056 KB |
Output is correct |
69 |
Correct |
449 ms |
85976 KB |
Output is correct |
70 |
Correct |
484 ms |
85008 KB |
Output is correct |
71 |
Correct |
489 ms |
85088 KB |
Output is correct |
72 |
Correct |
432 ms |
84596 KB |
Output is correct |
73 |
Correct |
1014 ms |
99016 KB |
Output is correct |
74 |
Correct |
798 ms |
91388 KB |
Output is correct |
75 |
Correct |
949 ms |
97784 KB |
Output is correct |
76 |
Correct |
1216 ms |
104440 KB |
Output is correct |
77 |
Correct |
653 ms |
88648 KB |
Output is correct |
78 |
Correct |
1171 ms |
99992 KB |
Output is correct |
79 |
Correct |
1199 ms |
101496 KB |
Output is correct |
80 |
Correct |
1267 ms |
104508 KB |
Output is correct |
81 |
Correct |
497 ms |
84520 KB |
Output is correct |
82 |
Correct |
938 ms |
97596 KB |
Output is correct |
83 |
Correct |
880 ms |
95864 KB |
Output is correct |
84 |
Correct |
1232 ms |
104376 KB |
Output is correct |
85 |
Correct |
788 ms |
93512 KB |
Output is correct |
86 |
Correct |
1012 ms |
97996 KB |
Output is correct |
87 |
Correct |
520 ms |
86856 KB |
Output is correct |
88 |
Correct |
973 ms |
98692 KB |
Output is correct |
89 |
Correct |
897 ms |
95648 KB |
Output is correct |
90 |
Correct |
973 ms |
97776 KB |
Output is correct |
91 |
Correct |
682 ms |
89744 KB |
Output is correct |
92 |
Correct |
1052 ms |
98252 KB |
Output is correct |
93 |
Correct |
542 ms |
88532 KB |
Output is correct |
94 |
Correct |
1000 ms |
98288 KB |
Output is correct |
95 |
Correct |
615 ms |
88820 KB |
Output is correct |
96 |
Correct |
982 ms |
97816 KB |
Output is correct |