#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#define pb push_back
#define mp make_pair
#define taskname "A"
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair<ll,int> ii;
typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const int maxn = 2e5 + 5;
const int inf = 1e9 + 1;
struct segTree{
int mx[maxn * 4];
int lz[maxn * 4];
int ans[maxn * 4];
void reset(){
fill_n(mx,maxn*4,0);
fill_n(lz,maxn*4,inf);
fill_n(ans,maxn*4,-1);
}
void push(int x , bool key){
ans[x] = max(ans[x],mx[x]-lz[x]);
if(key)lz[x*2] = min(lz[x*2],lz[x]),lz[x*2+1] = min(lz[x * 2 + 1],lz[x]);
lz[x] = inf;
}
void updateP(int x , int l , int r , int pos , int val){
push(x,l != r);
if(l == r){
mx[x] = val;
return;
}
int mid = l + r >> 1;
if(pos <= mid)updateP(x*2,l,mid,pos,val);
else updateP(x*2+1,mid+1,r,pos,val);
ans[x] = max(ans[x*2],ans[x*2+1]);
mx[x] = max(mx[x*2],mx[x * 2 + 1]);
}
void updateR(int x , int l , int r , int L , int R , int val){
push(x,l!=r);
if(l > R || L > r)return;
if(L <= l && r <= R){
lz[x] = min(lz[x],val);push(x,l!=r);return;
}
int mid = l + r >> 1;
updateR(x*2,l,mid,L,R,val);updateR(x*2+1,mid+1,r,L,R,val);
ans[x] = max(ans[x*2],ans[x*2+1]);
mx[x] = max(mx[x*2],mx[x * 2 + 1]);
}
int query(int x , int l , int r , int L , int R){
push(x,l!=r);
if(l > R || L > r)return -1;
if(L <= l && r <= R)return ans[x];
int mid = l + r >> 1;
return max(query(x*2,l,mid,L,R),query(x*2+1,mid+1,r,L,R));
}
}s;
int n , q;
int a[maxn],b[maxn],h[maxn];
ii queries[maxn];
int ans[maxn];
vector<ii> Q[maxn];
vector<int> avai[maxn];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
if(fopen(taskname".INP","r")){
freopen(taskname".INP", "r",stdin);
freopen(taskname".OUT", "w",stdout);
}
cin >> n;
for(int i = 1 ; i <= n ; ++i){
cin >> h[i] >> a[i] >> b[i];
}
cin >> q;
for(int i = 1 ; i <= q ; ++i){
cin >> queries[i].first >> queries[i].second;
ans[i] = -1;
}
{
//h[i] - h[j]
for(int i = 1 ; i <= q ; ++i){
Q[queries[i].second].pb(mp(queries[i].first,i));
}
s.reset();
for(int i = 1 ; i <= n ; ++i){
if(i + a[i] <= n){
avai[i + a[i]].pb(i);
}
if(i + b[i] + 1 <= n){
avai[i + b[i] + 1].pb(-i);
}
for(auto c : avai[i]){
if(c > 0)s.updateP(1,1,n,c,h[c]);
else s.updateP(1,1,n,-c,0);
// cout << i << " " << c << " " << h[c] << endl;
}
avai[i].clear();
s.updateR(1,1,n,i-b[i],i-a[i],h[i]);
// cout << s.mx[1] << endl;
// cout << i - b[i] << " " << i - a[i] << " " << h[i] << endl;
for(auto c : Q[i]){
ans[c.second] = max(ans[c.second],s.query(1,1,n,c.first,i));
}
Q[i].clear();
}
}
{
//-h[i] + h[j]
for(int i = 1 ; i <= q ; ++i){
Q[queries[i].first].pb(mp(queries[i].second,i));
}
s.reset();
for(int i = n ; i >= 1 ; --i){
if(i - a[i] >= 1){
avai[i - a[i]].pb(i);
}
if(i - b[i] - 1 >= 1){
avai[i - b[i] - 1].pb(-i);
}
for(auto c : avai[i]){
if(c > 0)s.updateP(1,1,n,c,h[c]);
else s.updateP(1,1,n,-c,0);
}
avai[i].clear();
s.updateR(1,1,n,i+a[i],i+b[i],h[i]);
for(auto c : Q[i]){
ans[c.second] = max(ans[c.second],s.query(1,1,n,i,c.first));
}
Q[i].clear();
}
}
for(int i = 1 ; i <= q ; ++i)cout << ans[i] << '\n';
}
Compilation message
antennas.cpp: In member function 'void segTree::updateP(int, int, int, int, int)':
antennas.cpp:40:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
antennas.cpp: In member function 'void segTree::updateR(int, int, int, int, int, int)':
antennas.cpp:52:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
antennas.cpp: In member function 'int segTree::query(int, int, int, int, int)':
antennas.cpp:61:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
antennas.cpp: In function 'int main()':
antennas.cpp:77:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen(taskname".INP", "r",stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:78:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen(taskname".OUT", "w",stdout);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
19196 KB |
Output is correct |
| 2 |
Incorrect |
18 ms |
19192 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
19196 KB |
Output is correct |
| 2 |
Incorrect |
18 ms |
19192 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
351 ms |
29692 KB |
Output is correct |
| 2 |
Correct |
423 ms |
31116 KB |
Output is correct |
| 3 |
Correct |
259 ms |
27384 KB |
Output is correct |
| 4 |
Correct |
423 ms |
30916 KB |
Output is correct |
| 5 |
Correct |
154 ms |
24440 KB |
Output is correct |
| 6 |
Correct |
408 ms |
30968 KB |
Output is correct |
| 7 |
Correct |
336 ms |
29304 KB |
Output is correct |
| 8 |
Correct |
405 ms |
30924 KB |
Output is correct |
| 9 |
Correct |
57 ms |
20984 KB |
Output is correct |
| 10 |
Incorrect |
398 ms |
30840 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
19196 KB |
Output is correct |
| 2 |
Incorrect |
18 ms |
19192 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
