This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 (stderr)
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 |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |