#include <bits/stdc++.h>
using namespace std;
const int INF = 2e9;
struct Seg{
vector<int> Smi, Sma;
int cap;
void init(int n){
for(cap = 1; cap < n; cap *= 2);
Smi.resize(2*cap, INF);
Sma.resize(2*cap);
}
void upd(int i, int v){
i += cap;
if(v > 0) Smi[i] = Sma[i] = v;
else Smi[i] = INF, Sma[i] = 0;
while(i > 1){
i /= 2;
Smi[i] = min(Smi[2*i], Smi[2*i+1]);
Sma[i] = max(Sma[2*i], Sma[2*i+1]);
}
}
pair<int, int> qry(int l, int r, int a, int b, int i){
if(l <= a && b <= r) return {Smi[i], Sma[i]};
if(r < a || b < l) return {INF, 0};
int m = (a+b)/2;
auto [mi1, ma1] = qry(l, r, a, m, 2*i);
auto [mi2, ma2] = qry(l, r, m+1, b, 2*i+1);
return {min(mi1, mi2), max(ma1, ma2)};
}
pair<int, int> qry(int l, int r){return qry(l, r, 1, cap, 1);}
};
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, q;
cin >> n;
vector<int> h(n), a(n), b(n);
for(int i = 0; i < n; i++) cin >> h[i] >> a[i] >> b[i];
cin >> q;
int qL, qR;
cin >> qL >> qR;
Seg seg;
seg.init(n);
vector<vector<pair<int, int>>> todo(n);
int ans = -1;
for(int i = 0; i < n; i++){
for(auto [j, v] : todo[i]){
seg.upd(j, v);
}
if(i+a[i]<n) todo[i+a[i]].emplace_back(i, h[i]);
if(i+b[i]+1<n) todo[i+b[i]+1].emplace_back(i, 0);
int l = max(0, i-b[i]);
int r = max(-1, i-a[i]);
if(r == -1) continue;
auto [mi, ma] = seg.qry(l+1, r+1);
ans = max(ans, max(h[i]-mi, ma-h[i]));
}
cout << ans << "\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
120 ms |
16604 KB |
Output is correct |
2 |
Correct |
147 ms |
16100 KB |
Output is correct |
3 |
Correct |
100 ms |
12956 KB |
Output is correct |
4 |
Correct |
131 ms |
16064 KB |
Output is correct |
5 |
Correct |
54 ms |
8396 KB |
Output is correct |
6 |
Correct |
162 ms |
16020 KB |
Output is correct |
7 |
Correct |
117 ms |
14620 KB |
Output is correct |
8 |
Correct |
134 ms |
16012 KB |
Output is correct |
9 |
Correct |
22 ms |
3108 KB |
Output is correct |
10 |
Correct |
138 ms |
15924 KB |
Output is correct |
11 |
Correct |
90 ms |
10188 KB |
Output is correct |
12 |
Correct |
146 ms |
15992 KB |
Output is correct |
13 |
Correct |
111 ms |
14696 KB |
Output is correct |
14 |
Correct |
115 ms |
14588 KB |
Output is correct |
15 |
Correct |
101 ms |
14716 KB |
Output is correct |
16 |
Correct |
102 ms |
15292 KB |
Output is correct |
17 |
Correct |
125 ms |
14892 KB |
Output is correct |
18 |
Correct |
108 ms |
15312 KB |
Output is correct |
19 |
Correct |
104 ms |
14652 KB |
Output is correct |
20 |
Correct |
106 ms |
14680 KB |
Output is correct |
21 |
Correct |
96 ms |
14440 KB |
Output is correct |
22 |
Correct |
96 ms |
14508 KB |
Output is correct |
23 |
Correct |
112 ms |
14620 KB |
Output is correct |
24 |
Correct |
121 ms |
14844 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |