#pragma GCC target ("avx2")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("O3")
#include "bits/stdc++.h"
#include <unordered_set>
#include <unordered_map>
#include <random>
using namespace std;
typedef long long ll;
const ll MOD = 1'000'000'007LL; /*998'244'353LL;*/
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
const int dx[4]={ 1,0,-1,0 };
const int dy[4]={ 0,1,0,-1 };
int N;
int H[200000], A[200000], B[2000000];
int Q;
int L[200000], R[200000];
ll ans[200000];
void chmax(ll &a, ll b){
a = max(a, b);
}
void print();
struct SegmentTree{
int N;
struct Node{
int flg = 0;
ll minLiv = 1e15L;
ll maxAns = -1e15L;
Node operator*(const Node &r){
Node ret;
ret.flg = this->flg + r.flg;
ret.minLiv = min(this->minLiv, r.minLiv);
ret.maxAns = max(this->maxAns, r.maxAns);
return ret;
}
};
vector<Node> node;
struct Lazy{
bool flg = false;
ll H = -1e15L;
};
vector<Lazy> lazy;
public:
void init(int n){
node.clear();
lazy.clear();
N = 1;
while(N < n) N = (N<<1);
node.resize(2*N-1, Node());
lazy.resize(2*N-1, Lazy());
}
void eval(int k, int l, int r){
if(lazy[k].flg){
chmax(node[k].maxAns, lazy[k].H - node[k].minLiv);
if(r-l > 1){
lazy[(k<<1)+1].flg = true;
chmax(lazy[(k<<1)+1].H, lazy[k].H);
lazy[(k<<1)+2].flg = true;
chmax(lazy[(k<<1)+2].H, lazy[k].H);
}
lazy[k] = Lazy();
}
}
void update(int a, int b, ll x, int k=0, int l=0, int r=-1){
if(a >= b) return;
if(r == -1) r = N;
eval(k, l, r);
if(b <= l || r <= a) return;
if(a <= l && r <= b){
lazy[k].H = x;
lazy[k].flg = true;
eval(k, l, r);
}
else{
update(a, b, x, (k<<1)+1, l, (l+r)>>1);
update(a, b, x, (k<<1)+2, (l+r)>>1, r);
node[k] = node[(k<<1)+1] * node[(k<<1)+2];
}
}
void build(int a, int k=0, int l=0, int r=-1){
if(r == -1) r = N;
eval(k, l, r);
if(r-l == 1){
node[k].flg = 1;
node[k].minLiv = H[l];
while(k > 0){
k = (k-1) >> 1;
node[k] = node[(k<<1)+1] * node[(k<<1)+2];
}
return;
}
if(a < (l+r)/2){
eval((k<<1)+2, (l+r)>>1, r);
build(a, (k<<1)+1, l, (l+r)>>1);
}
else{
eval((k<<1)+1, l, (l+r)>>1);
build(a, (k<<1)+2, (l+r)>>1, r);
}
}
void dest(int a, int k=0, int l=0, int r=-1){
if(r == -1) r = N;
eval(k, l, r);
if(r-l == 1){
node[k].flg = 0;
node[k].minLiv = 1e15L;
while(k > 0){
k = (k-1) >> 1;
node[k] = node[(k<<1)+1] * node[(k<<1)+2];
}
return;
}
if(a < (l+r)/2){
eval((k<<1)+2, (l+r)>>1, r);
dest(a, (k<<1)+1, l, (l+r)>>1);
}
else{
eval((k<<1)+1, l, (l+r)>>1);
dest(a, (k<<1)+2, (l+r)>>1, r);
}
}
ll query(int a, int b, int k=0, int l=0, int r=-1){
if(a >= b) return -1;
if(r == -1) r = N;
if(b <= l || r <= a) return -1;
eval(k, l, r);
if(a <= l && r <= b) return node[k].maxAns;
return max(query(a, b, (k<<1)+1, l, (l+r)>>1), query(a, b, (k<<1)+2, (l+r)>>1, r));
}
};
SegmentTree st;
priority_queue<pair<int, int>> pq;
priority_queue<pair<int, int>> ask;
void print(){
rep(i, 2*st.N-1){
cout << st.node[i].minLiv << " ";
}
cout << endl;
rep(i, 2*st.N-1){
cout << st.node[i].maxAns << " ";
}
cout << endl;
rep(i, 2*st.N-1){
cout << st.lazy[i].H << " ";
}
cout << endl;
}
signed main(){
cin >> N;
rep(i, N){
cin >> H[i] >> A[i] >> B[i];
}
cin >> Q;
rep(i, Q){
cin >> L[i] >> R[i];
L[i]--;
}
rep(i, Q) ans[i] = -1;
rep(i, Q) ask.push({ -R[i],i });
st.init(N);
rep(i, N+1){
while(!ask.empty() && -ask.top().first == i){
int n = ask.top().second;
ask.pop();
chmax(ans[n], st.query(L[n], R[n]));
}
while(!pq.empty() && -pq.top().first == i){
int n = pq.top().second;
pq.pop();
if(i == n+A[n]){
st.build(n);
}
else if(i == n+B[n]+1){
st.dest(n);
}
}
if(i == N) break;
st.update(max(0, i-B[i]), max(0,i-A[i]+1), H[i]);
pq.push({ -(i+A[i]),i });
pq.push({ -(i+B[i]+1),i });
}
rep(i, N) H[i] = 1e9L+1-H[i];
rep(i, Q) ask.push({ -R[i],i });
st.init(N);
rep(i, N+1){
while(!ask.empty() && -ask.top().first == i){
int n = ask.top().second;
ask.pop();
chmax(ans[n], st.query(L[n], R[n]));
//cout << "QUERY " << n << " = " << st.query(L[n], R[n]) << endl;
}
while(!pq.empty() && -pq.top().first == i){
int n = pq.top().second;
pq.pop();
if(i == n+A[n]){
st.build(n);
//cout << "BUILD " << n << endl;
}
else if(i == n+B[n]+1){
st.dest(n);
//cout << "DESTROY " << n << endl;
}
//print();
}
if(i == N) break;
st.update(max(0, i-B[i]), max(0, i-A[i]+1), H[i]);
//cout << "UPDATE " << i << endl;
//print();
pq.push({ -(i+A[i]),i });
pq.push({ -(i+B[i]+1),i });
}
rep(i, Q){
cout << ans[i] << endl;
}
}
/*
5
10 2 4
1 1 1
2 1 3
1 1 1
100 1 1
5
1 2
2 3
1 3
1 4
1 5
20
260055884 2 15
737689751 5 5
575359903 1 15
341907415 14 14
162026576 9 19
55126745 10 19
95712405 11 14
416027186 8 13
370819848 11 14
629309664 4 13
822713895 5 15
390716905 13 17
577166133 8 19
195931195 10 17
377030463 14 17
968486685 11 19
963040581 4 10
566835557 1 12
586336111 6 16
385865831 8 9
1
1 20
*/
Compilation message
antennas.cpp: In function 'void print()':
antennas.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
| ^
antennas.cpp:145:5: note: in expansion of macro 'rep'
145 | rep(i, 2*st.N-1){
| ^~~
antennas.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
| ^
antennas.cpp:149:5: note: in expansion of macro 'rep'
149 | rep(i, 2*st.N-1){
| ^~~
antennas.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
| ^
antennas.cpp:153:5: note: in expansion of macro 'rep'
153 | rep(i, 2*st.N-1){
| ^~~
antennas.cpp: In function 'int main()':
antennas.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
| ^
antennas.cpp:161:5: note: in expansion of macro 'rep'
161 | rep(i, N){
| ^~~
antennas.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
| ^
antennas.cpp:165:5: note: in expansion of macro 'rep'
165 | rep(i, Q){
| ^~~
antennas.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
| ^
antennas.cpp:170:5: note: in expansion of macro 'rep'
170 | rep(i, Q) ans[i] = -1;
| ^~~
antennas.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
| ^
antennas.cpp:172:5: note: in expansion of macro 'rep'
172 | rep(i, Q) ask.push({ -R[i],i });
| ^~~
antennas.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
| ^
antennas.cpp:174:5: note: in expansion of macro 'rep'
174 | rep(i, N+1){
| ^~~
antennas.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
| ^
antennas.cpp:199:5: note: in expansion of macro 'rep'
199 | rep(i, N) H[i] = 1e9L+1-H[i];
| ^~~
antennas.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
| ^
antennas.cpp:200:5: note: in expansion of macro 'rep'
200 | rep(i, Q) ask.push({ -R[i],i });
| ^~~
antennas.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
| ^
antennas.cpp:202:5: note: in expansion of macro 'rep'
202 | rep(i, N+1){
| ^~~
antennas.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
| ^
antennas.cpp:235:5: note: in expansion of macro 'rep'
235 | rep(i, Q){
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
2 ms |
332 KB |
Output is correct |
3 |
Correct |
2 ms |
332 KB |
Output is correct |
4 |
Correct |
2 ms |
332 KB |
Output is correct |
5 |
Correct |
2 ms |
332 KB |
Output is correct |
6 |
Correct |
2 ms |
332 KB |
Output is correct |
7 |
Correct |
2 ms |
332 KB |
Output is correct |
8 |
Correct |
2 ms |
296 KB |
Output is correct |
9 |
Correct |
2 ms |
332 KB |
Output is correct |
10 |
Correct |
2 ms |
304 KB |
Output is correct |
11 |
Correct |
2 ms |
300 KB |
Output is correct |
12 |
Correct |
3 ms |
332 KB |
Output is correct |
13 |
Correct |
2 ms |
332 KB |
Output is correct |
14 |
Correct |
2 ms |
332 KB |
Output is correct |
15 |
Correct |
2 ms |
304 KB |
Output is correct |
16 |
Correct |
3 ms |
312 KB |
Output is correct |
17 |
Correct |
2 ms |
332 KB |
Output is correct |
18 |
Correct |
4 ms |
308 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
2 ms |
332 KB |
Output is correct |
21 |
Correct |
2 ms |
332 KB |
Output is correct |
22 |
Correct |
2 ms |
304 KB |
Output is correct |
23 |
Correct |
2 ms |
332 KB |
Output is correct |
24 |
Correct |
3 ms |
304 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
2 ms |
332 KB |
Output is correct |
3 |
Correct |
2 ms |
332 KB |
Output is correct |
4 |
Correct |
2 ms |
332 KB |
Output is correct |
5 |
Correct |
2 ms |
332 KB |
Output is correct |
6 |
Correct |
2 ms |
332 KB |
Output is correct |
7 |
Correct |
2 ms |
332 KB |
Output is correct |
8 |
Correct |
2 ms |
296 KB |
Output is correct |
9 |
Correct |
2 ms |
332 KB |
Output is correct |
10 |
Correct |
2 ms |
304 KB |
Output is correct |
11 |
Correct |
2 ms |
300 KB |
Output is correct |
12 |
Correct |
3 ms |
332 KB |
Output is correct |
13 |
Correct |
2 ms |
332 KB |
Output is correct |
14 |
Correct |
2 ms |
332 KB |
Output is correct |
15 |
Correct |
2 ms |
304 KB |
Output is correct |
16 |
Correct |
3 ms |
312 KB |
Output is correct |
17 |
Correct |
2 ms |
332 KB |
Output is correct |
18 |
Correct |
4 ms |
308 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
2 ms |
332 KB |
Output is correct |
21 |
Correct |
2 ms |
332 KB |
Output is correct |
22 |
Correct |
2 ms |
304 KB |
Output is correct |
23 |
Correct |
2 ms |
332 KB |
Output is correct |
24 |
Correct |
3 ms |
304 KB |
Output is correct |
25 |
Correct |
442 ms |
6340 KB |
Output is correct |
26 |
Correct |
54 ms |
1344 KB |
Output is correct |
27 |
Correct |
614 ms |
8872 KB |
Output is correct |
28 |
Correct |
613 ms |
8808 KB |
Output is correct |
29 |
Correct |
482 ms |
6324 KB |
Output is correct |
30 |
Correct |
410 ms |
6168 KB |
Output is correct |
31 |
Correct |
622 ms |
8024 KB |
Output is correct |
32 |
Correct |
622 ms |
8824 KB |
Output is correct |
33 |
Correct |
586 ms |
8236 KB |
Output is correct |
34 |
Correct |
299 ms |
4652 KB |
Output is correct |
35 |
Correct |
626 ms |
8808 KB |
Output is correct |
36 |
Correct |
679 ms |
8956 KB |
Output is correct |
37 |
Correct |
346 ms |
4752 KB |
Output is correct |
38 |
Correct |
640 ms |
7776 KB |
Output is correct |
39 |
Correct |
86 ms |
1604 KB |
Output is correct |
40 |
Correct |
626 ms |
7920 KB |
Output is correct |
41 |
Correct |
468 ms |
6076 KB |
Output is correct |
42 |
Correct |
605 ms |
7868 KB |
Output is correct |
43 |
Correct |
198 ms |
2980 KB |
Output is correct |
44 |
Correct |
606 ms |
7840 KB |
Output is correct |
45 |
Correct |
107 ms |
1908 KB |
Output is correct |
46 |
Correct |
611 ms |
8032 KB |
Output is correct |
47 |
Correct |
152 ms |
2492 KB |
Output is correct |
48 |
Correct |
600 ms |
7820 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
707 ms |
31208 KB |
Output is correct |
2 |
Correct |
794 ms |
32072 KB |
Output is correct |
3 |
Correct |
522 ms |
29880 KB |
Output is correct |
4 |
Correct |
846 ms |
31972 KB |
Output is correct |
5 |
Correct |
314 ms |
15816 KB |
Output is correct |
6 |
Correct |
841 ms |
31900 KB |
Output is correct |
7 |
Correct |
704 ms |
31092 KB |
Output is correct |
8 |
Correct |
829 ms |
31848 KB |
Output is correct |
9 |
Correct |
87 ms |
5052 KB |
Output is correct |
10 |
Correct |
762 ms |
31980 KB |
Output is correct |
11 |
Correct |
438 ms |
18996 KB |
Output is correct |
12 |
Correct |
814 ms |
32008 KB |
Output is correct |
13 |
Correct |
495 ms |
31908 KB |
Output is correct |
14 |
Correct |
489 ms |
31796 KB |
Output is correct |
15 |
Correct |
468 ms |
31804 KB |
Output is correct |
16 |
Correct |
447 ms |
31776 KB |
Output is correct |
17 |
Correct |
529 ms |
31856 KB |
Output is correct |
18 |
Correct |
470 ms |
31884 KB |
Output is correct |
19 |
Correct |
466 ms |
31840 KB |
Output is correct |
20 |
Correct |
457 ms |
31796 KB |
Output is correct |
21 |
Correct |
492 ms |
31716 KB |
Output is correct |
22 |
Correct |
474 ms |
31816 KB |
Output is correct |
23 |
Correct |
494 ms |
31796 KB |
Output is correct |
24 |
Correct |
446 ms |
31752 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
2 ms |
332 KB |
Output is correct |
3 |
Correct |
2 ms |
332 KB |
Output is correct |
4 |
Correct |
2 ms |
332 KB |
Output is correct |
5 |
Correct |
2 ms |
332 KB |
Output is correct |
6 |
Correct |
2 ms |
332 KB |
Output is correct |
7 |
Correct |
2 ms |
332 KB |
Output is correct |
8 |
Correct |
2 ms |
296 KB |
Output is correct |
9 |
Correct |
2 ms |
332 KB |
Output is correct |
10 |
Correct |
2 ms |
304 KB |
Output is correct |
11 |
Correct |
2 ms |
300 KB |
Output is correct |
12 |
Correct |
3 ms |
332 KB |
Output is correct |
13 |
Correct |
2 ms |
332 KB |
Output is correct |
14 |
Correct |
2 ms |
332 KB |
Output is correct |
15 |
Correct |
2 ms |
304 KB |
Output is correct |
16 |
Correct |
3 ms |
312 KB |
Output is correct |
17 |
Correct |
2 ms |
332 KB |
Output is correct |
18 |
Correct |
4 ms |
308 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
2 ms |
332 KB |
Output is correct |
21 |
Correct |
2 ms |
332 KB |
Output is correct |
22 |
Correct |
2 ms |
304 KB |
Output is correct |
23 |
Correct |
2 ms |
332 KB |
Output is correct |
24 |
Correct |
3 ms |
304 KB |
Output is correct |
25 |
Correct |
442 ms |
6340 KB |
Output is correct |
26 |
Correct |
54 ms |
1344 KB |
Output is correct |
27 |
Correct |
614 ms |
8872 KB |
Output is correct |
28 |
Correct |
613 ms |
8808 KB |
Output is correct |
29 |
Correct |
482 ms |
6324 KB |
Output is correct |
30 |
Correct |
410 ms |
6168 KB |
Output is correct |
31 |
Correct |
622 ms |
8024 KB |
Output is correct |
32 |
Correct |
622 ms |
8824 KB |
Output is correct |
33 |
Correct |
586 ms |
8236 KB |
Output is correct |
34 |
Correct |
299 ms |
4652 KB |
Output is correct |
35 |
Correct |
626 ms |
8808 KB |
Output is correct |
36 |
Correct |
679 ms |
8956 KB |
Output is correct |
37 |
Correct |
346 ms |
4752 KB |
Output is correct |
38 |
Correct |
640 ms |
7776 KB |
Output is correct |
39 |
Correct |
86 ms |
1604 KB |
Output is correct |
40 |
Correct |
626 ms |
7920 KB |
Output is correct |
41 |
Correct |
468 ms |
6076 KB |
Output is correct |
42 |
Correct |
605 ms |
7868 KB |
Output is correct |
43 |
Correct |
198 ms |
2980 KB |
Output is correct |
44 |
Correct |
606 ms |
7840 KB |
Output is correct |
45 |
Correct |
107 ms |
1908 KB |
Output is correct |
46 |
Correct |
611 ms |
8032 KB |
Output is correct |
47 |
Correct |
152 ms |
2492 KB |
Output is correct |
48 |
Correct |
600 ms |
7820 KB |
Output is correct |
49 |
Correct |
707 ms |
31208 KB |
Output is correct |
50 |
Correct |
794 ms |
32072 KB |
Output is correct |
51 |
Correct |
522 ms |
29880 KB |
Output is correct |
52 |
Correct |
846 ms |
31972 KB |
Output is correct |
53 |
Correct |
314 ms |
15816 KB |
Output is correct |
54 |
Correct |
841 ms |
31900 KB |
Output is correct |
55 |
Correct |
704 ms |
31092 KB |
Output is correct |
56 |
Correct |
829 ms |
31848 KB |
Output is correct |
57 |
Correct |
87 ms |
5052 KB |
Output is correct |
58 |
Correct |
762 ms |
31980 KB |
Output is correct |
59 |
Correct |
438 ms |
18996 KB |
Output is correct |
60 |
Correct |
814 ms |
32008 KB |
Output is correct |
61 |
Correct |
495 ms |
31908 KB |
Output is correct |
62 |
Correct |
489 ms |
31796 KB |
Output is correct |
63 |
Correct |
468 ms |
31804 KB |
Output is correct |
64 |
Correct |
447 ms |
31776 KB |
Output is correct |
65 |
Correct |
529 ms |
31856 KB |
Output is correct |
66 |
Correct |
470 ms |
31884 KB |
Output is correct |
67 |
Correct |
466 ms |
31840 KB |
Output is correct |
68 |
Correct |
457 ms |
31796 KB |
Output is correct |
69 |
Correct |
492 ms |
31716 KB |
Output is correct |
70 |
Correct |
474 ms |
31816 KB |
Output is correct |
71 |
Correct |
494 ms |
31796 KB |
Output is correct |
72 |
Correct |
446 ms |
31752 KB |
Output is correct |
73 |
Correct |
1400 ms |
37644 KB |
Output is correct |
74 |
Correct |
902 ms |
32516 KB |
Output is correct |
75 |
Correct |
1420 ms |
37672 KB |
Output is correct |
76 |
Correct |
1740 ms |
41048 KB |
Output is correct |
77 |
Correct |
930 ms |
22196 KB |
Output is correct |
78 |
Correct |
1455 ms |
37980 KB |
Output is correct |
79 |
Correct |
1630 ms |
39564 KB |
Output is correct |
80 |
Correct |
1847 ms |
41216 KB |
Output is correct |
81 |
Correct |
822 ms |
14184 KB |
Output is correct |
82 |
Correct |
1265 ms |
36116 KB |
Output is correct |
83 |
Correct |
1398 ms |
26432 KB |
Output is correct |
84 |
Correct |
1808 ms |
41032 KB |
Output is correct |
85 |
Correct |
1008 ms |
36024 KB |
Output is correct |
86 |
Correct |
1294 ms |
39164 KB |
Output is correct |
87 |
Correct |
577 ms |
32748 KB |
Output is correct |
88 |
Correct |
1296 ms |
39172 KB |
Output is correct |
89 |
Correct |
1087 ms |
37164 KB |
Output is correct |
90 |
Correct |
1331 ms |
39236 KB |
Output is correct |
91 |
Correct |
740 ms |
34272 KB |
Output is correct |
92 |
Correct |
1305 ms |
39172 KB |
Output is correct |
93 |
Correct |
630 ms |
32952 KB |
Output is correct |
94 |
Correct |
1350 ms |
39148 KB |
Output is correct |
95 |
Correct |
673 ms |
33740 KB |
Output is correct |
96 |
Correct |
1283 ms |
39108 KB |
Output is correct |