#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
const int inf = 1e9;
int n, Q;
///SEGMENT TREE BEGIN
static int lazy[400005]; ///smallest height of the right antenna
static int tree[400005]; ///Max Hi if active, else -INF.
static int histMax[400005]; ///histMax = max(tree[i] - lazy[i]);
inline void reset(){
fill(tree,tree+2*n,-inf);
fill(lazy,lazy+2*n,inf);
fill(histMax,histMax+2*n,-inf);
}
inline void relax(int i){
if(i < n) histMax[i] = max(histMax[i<<1], histMax[i<<1|1]);
histMax[i] = max(tree[i] - lazy[i], histMax[i]);
}
void prop(int i){
if(i != 1) prop(i >> 1);
lazy[i<<1] = min(lazy[i<<1], lazy[i]);
relax(i<<1);
lazy[i<<1|1] = min(lazy[i<<1|1], lazy[i]);
relax(i<<1|1);
lazy[i] = inf;
}
inline void ptupdate(int i, int v){
//cout << "Pt: " << i << " " << v << "\n";
i += n;
prop(i >> 1); lazy[i] = inf;
tree[i] = v; relax(i);
for(i >>= 1;i > 0;i >>= 1) tree[i] = max(tree[i<<1], tree[i<<1|1]), relax(i);
}
inline void update(int L, int R, int v){
//cout << "Lazy: " << L << " " << R-1 << " " << v << "\n";
for(int l = L + n, r = R + n;l < r;l >>= 1,r >>= 1){
if(l&1){
lazy[l] = min(lazy[l], v);
relax(l);
l++;
}
if(r&1){
r--;
lazy[r] = min(lazy[r], v);
relax(r);
}
}
for(L += n;L > 0;L >>= 1) relax(L);
for(R += n-1;R > 0;R >>= 1) relax(R);
}
inline int query(int l, int r){
int ans = -inf;
prop((l+n) >> 1);
prop((r-1+n) >> 1);
for(l += n,r += n;l < r;l >>= 1,r >>= 1){
if(l&1){
//if(l == 5 && r == 8) cout << histMax[l] << "FUNNYTHING\n";
ans = max(ans,histMax[l]);
l++;
}
if(r&1){
r--;
ans = max(ans,histMax[r]);
}
}
return ans;
}
///SEGMENT TREE END
int H[200005];
int A[200005];
int B[200005];
int ans[200005];
ii QQ[200005];
vector<ii> queries[200005];
vector<ii> events[200005];
void solve(){
for(int i = 0;i < n;i++) events[i].clear();
for(int i = 0;i < Q;i++) queries[i].clear();
reset();
for(int i = 0;i < n;i++){
int start = i + A[i], end = i + B[i] + 1;
if(start < n) events[start].push_back(ii(i, 1)); ///1 is start
if(end < n) events[end].push_back(ii(i, -1)); ///-1 is end
}
for(int i = 0;i < Q;i++){
queries[QQ[i].second].push_back(ii(QQ[i].first, i));
}
for(int r = 0;r < n;r++){
//cout << r << ":\n";
for(ii e : events[r]){
if(e.second == 1) ptupdate(e.first, H[e.first]);
else ptupdate(e.first, -inf);
}
if(r - A[r] >= 0){
int R = r - A[r];
int L = max(0, r - B[r]);
update(L, R+1, H[r]);
}
for(ii q : queries[r]){
int res = query(q.first, r+1);
//cout << q.first << " " << r << " " << res << "\n";
ans[q.second] = max(ans[q.second],res);
}
}
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 0;i < n;i++) cin >> H[i] >> A[i] >> B[i];
cin >> Q;
fill(ans,ans+Q, -inf);
for(int i = 0;i < Q;i++){
int l, r; cin >> l >> r; l--; r--;
QQ[i] = ii(l,r);
}
solve();
reverse(H,H+n);
reverse(A,A+n);
reverse(B,B+n);
for(int i = 0;i < Q;i++){
QQ[i].first = n - 1 - QQ[i].first;
QQ[i].second = n - 1 - QQ[i].second;
swap(QQ[i].first,QQ[i].second);
}
solve();
for(int i = 0;i < Q;i++) cout << max(-1,ans[i]) << "\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
10 ms |
9728 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
10 ms |
9728 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
252 ms |
24312 KB |
Output is correct |
2 |
Correct |
319 ms |
25976 KB |
Output is correct |
3 |
Correct |
198 ms |
21112 KB |
Output is correct |
4 |
Correct |
298 ms |
25976 KB |
Output is correct |
5 |
Correct |
118 ms |
17144 KB |
Output is correct |
6 |
Correct |
298 ms |
25948 KB |
Output is correct |
7 |
Correct |
273 ms |
23928 KB |
Output is correct |
8 |
Correct |
309 ms |
25976 KB |
Output is correct |
9 |
Correct |
43 ms |
12288 KB |
Output is correct |
10 |
Correct |
308 ms |
25848 KB |
Output is correct |
11 |
Correct |
174 ms |
19960 KB |
Output is correct |
12 |
Correct |
295 ms |
25976 KB |
Output is correct |
13 |
Correct |
247 ms |
26092 KB |
Output is correct |
14 |
Correct |
229 ms |
25780 KB |
Output is correct |
15 |
Correct |
221 ms |
24980 KB |
Output is correct |
16 |
Correct |
214 ms |
25020 KB |
Output is correct |
17 |
Correct |
253 ms |
26540 KB |
Output is correct |
18 |
Correct |
227 ms |
25412 KB |
Output is correct |
19 |
Correct |
232 ms |
25708 KB |
Output is correct |
20 |
Correct |
228 ms |
25708 KB |
Output is correct |
21 |
Correct |
236 ms |
25708 KB |
Output is correct |
22 |
Correct |
235 ms |
25712 KB |
Output is correct |
23 |
Correct |
232 ms |
25804 KB |
Output is correct |
24 |
Correct |
221 ms |
24304 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
10 ms |
9728 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |