#include "bits/stdc++.h"
using namespace std;
#define ar array
typedef long long ll;
#define int ll
#define sow cerr<<"here"<<endl;
const int N = 2e5 + 5;
const int inf = 2e9;
struct ST{
int tree[N << 2], mx[N << 2];
int cost[N << 2];
void init(){
memset(tree, 0, sizeof tree);
memset(cost, 0, sizeof cost);
memset(mx, 0, sizeof mx);
}
void push(int x, int lx, int rx){
if(lx == rx) return;
mx[x << 1] = max(mx[x << 1], mx[x]);
mx[x << 1 | 1] = max(mx[x << 1 | 1], mx[x]);
cost[x << 1] = max(cost[x << 1], mx[x << 1] - tree[x << 1]);
cost[x << 1 | 1] = max(cost[x << 1 | 1], mx[x << 1 | 1] - tree[x << 1 | 1]);
mx[x] = 0;
}
void set(int i, int v, int lx = 0, int rx = N, int x = 1){
if(lx == rx){
tree[x] = v, mx[x] = 0;
cost[x] = -1;
return;
} int m = (lx + rx) >> 1;
push(x, lx, rx);
if(i <= m) set(i, v, lx, m, x << 1);
else set(i, v, m + 1, rx, x << 1 | 1);
tree[x] = min(tree[x << 1], tree[x << 1 | 1]);
cost[x] = max(cost[x << 1], cost[x << 1 | 1]);
}
void add(int l, int r, int v, int lx = 0, int rx = N, int x = 1){
if(lx > r || rx < l) return;
if(lx >= l && rx <= r){
mx[x] = max(mx[x], v);
cost[x] = max(cost[x], mx[x] - tree[x]);
//~ cout<<lx<<" "<<rx<<" "<<v<<" "<<cost[x]<<" <-\n";
return;
} int m = (lx + rx) >> 1;
push(x, lx, rx);
add(l, r, v, lx, m, x << 1);
add(l, r, v, m + 1, rx, x << 1 | 1);
cost[x] = max(cost[x << 1], cost[x << 1 | 1]);
}
int get(int l, int r, int lx = 0, int rx = N, int x = 1){
if(lx > r || rx < l) return -inf;
if(lx >= l && rx <= r){
//~ cout<<lx<<" "<<rx<<" "<<cost[x]<<endl;
return cost[x];
} int m = (lx + rx) >> 1;
push(x, lx, rx);
return max(get(l, r, lx, m, x << 1), get(l, r, m + 1, rx, x << 1 | 1));
}
int get2(int l, int r, int lx = 0, int rx = N, int x = 1){
if(lx > r || rx < l) return -inf;
if(lx >= l && rx <= r){
return mx[x];
} int m = (lx + rx) >> 1;
push(x, lx, rx);
return max(get2(l, r, lx, m, x << 1), get2(l, r, m + 1, rx, x << 1 | 1));
}
int pos(int i, int lx = 0, int rx = N, int x = 1){
if(lx == rx) return tree[x];
int m = (lx + rx) >> 1;
push(x, lx, rx);
if(i <= m) return pos(i, lx, m, x << 1);
else return pos(i, m + 1, rx, x << 1 | 1);
}
}tree;
int h[N], a[N], b[N];
int l[N], r[N], res[N];
vector<ar<int, 2>> Q[N];
int n, q;
int mx[N], mn[N];
int cost[N];
/*
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
*/
void solve(){
tree.init();
vector<int> p(q); iota(p.begin(), p.end(), 0);
sort(p.begin(), p.end(), [&](int i, int j){
return r[i] < r[j];
});
auto set = [&](int i, int v){
mn[i] = v, mx[i] = 0, cost[i] = -1;
};
for(int i=0;i<n;i++){
//~ tree.set(i, inf);
set(i, inf);
}
auto add = [&](int l, int r, int v){
for(int i=l;i<=r;i++){
mx[i] = max(mx[i], v);
cost[i] = max(cost[i], mx[i] - mn[i]);
}
};
auto get = [&](int l, int r){
int res = 0;
for(int i=l;i<=r;i++){
res = max(res, cost[i]);
}
return res;
};
int j = 0;
for(int i=0;i<n;i++){
for(auto [j, t] : Q[i]){
if(t){
set(j, h[j]);
//~ tree.set(j, h[j]);
} else {
set(j, inf);
//~ tree.set(j, inf);
}
} Q[i].clear();
//~ for(int j=0;j<n;j++) cout<<tree.get2(j, j)<<" ";
//~ cout<<"\n";
//~ for(int j=0;j<n;j++) cout<<tree.get(j, j)<<" ";
//~ cout<<"\n";
//~ for(int j=0;j<n;j++) cout<<tree.pos(j)<<" ";
//~ cout<<"\n";
int L = max(i - b[i], 0ll), R = i - a[i];
if(L <= R){
//~ cout<<L<<" "<<R<<" "<<h[i]<<"\n";
//~ tree.add(L, R, h[i]);
add(L, R, h[i]);
}
//~ cout<<"s\n";
//~ for(int j=0;j<n;j++) tree.get(j, j);
//~ cout<<"e"<<endl;
Q[min(i + a[i], n)].push_back({i, 1});
Q[min(i + b[i] + 1, n)].push_back({i, 0});
while(j < q && r[p[j]] == i){
//~ res[p[j]] = max(res[p[j]], tree.get(l[p[j]], r[p[j]]));
res[p[j]] = max(res[p[j]], get(l[p[j]], r[p[j]]));
j++;
}
} Q[n].clear();
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
freopen("in.txt", "r", stdin);
//~ freopen("out.txt", "r", stdin);
cin >> n;
for(int i=0;i<n;i++) cin >> h[i] >> a[i] >> b[i];
cin >> q;
for(int i=0;i<q;i++){
cin >> l[i] >> r[i];
l[i]--, r[i]--;
}
memset(res, -1, sizeof res);
solve();
reverse(h, h + n);
reverse(a, a + n);
reverse(b, b + n);
for(int i=0;i<q;i++) l[i] = n - l[i] - 1, r[i] = n - r[i] - 1, swap(l[i], r[i]);
solve();
for(int i=0;i<q;i++) cout<<res[i]<<"\n";
}
Compilation message
antennas.cpp: In function 'int main()':
antennas.cpp:179:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
179 | freopen("in.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
15 ms |
25392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
15 ms |
25392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
14 ms |
25428 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
15 ms |
25392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
