#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4")
#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
#define int ll
const int mxn = 2e5+10;
const ll inf = 1e9+10;
#define ls now*2+1
#define rs now*2+2
#define mid ((l+r)>>1)
struct SEG1{
struct node{
int mn,mx,val;
node(){
mn = inf,mx = 0,val = -1;
}
};
node seg[mxn*4];
SEG1(){}
node pull(node a,node b){
node re;
re.mn = min(a.mn,b.mn);
re.mx = 0;
re.val = max(a.val,b.val);
return re;
}
void push(int now,int l,int r){
seg[ls].mx = max(seg[ls].mx,seg[now].mx);
seg[rs].mx = max(seg[rs].mx,seg[now].mx);
seg[ls].val = max(seg[ls].val,seg[ls].mx-seg[ls].mn);
seg[rs].val = max(seg[rs].val,seg[rs].mx-seg[rs].mn);
seg[now].mx = 0;
return;
}
void chmax(int now,int l,int r,int s,int e,int v){
if(l>=s&&e>=r){
seg[now].mx = max(seg[now].mx,v);
seg[now].val = max(seg[now].val,seg[now].mx-seg[now].mn);
return;
}
push(now,l,r);
if(mid>=s)chmax(ls,l,mid,s,e,v);
if(mid<e)chmax(rs,mid+1,r,s,e,v);
seg[now].mn = min(seg[ls].mn,seg[rs].mn);
seg[now].val = max(seg[ls].val,seg[rs].val);
return;
}
void chmin(int now,int l,int r,int p,int v){
if(l == r){
seg[now].mn = v;seg[now].mx = 0;
seg[now].val = seg[now].mx-seg[now].mn;
return;
}
push(now,l,r);
if(mid>=p)chmin(ls,l,mid,p,v);
else chmin(rs,mid+1,r,p,v);
seg[now] = pull(seg[ls],seg[rs]);
return;
}
node getval(int now,int l,int r,int s,int e){
if(l>=s&&e>=r)return seg[now];
push(now,l,r);
if(mid>=e)return getval(ls,l,mid,s,e);
else if(mid<s)return getval(rs,mid+1,r,s,e);
else return pull(getval(ls,l,mid,s,e),getval(rs,mid+1,r,s,e));
}
void init(){
for(auto &i:seg)i.mn = inf,i.mx = 0,i.val = -1;
return;
}
};
struct SEG2{
int seg[mxn*4];
SEG2(){
for(auto &i:seg)i = -1;
}
void modify(int now,int l,int r,int p,int v){
if(l == r){
seg[now] = v;
return;
}
if(mid>=p)modify(ls,l,mid,p,v);
else modify(rs,mid+1,r,p,v);
seg[now] = max(seg[ls],seg[rs]);
return;
}
int getval(int now,int l,int r,int s,int e){
if(l>=s&&e>=r)return seg[now];
if(mid>=e)return getval(ls,l,mid,s,e);
else if(mid<s)return getval(rs,mid+1,r,s,e);
else return max(getval(ls,l,mid,s,e),getval(rs,mid+1,r,s,e));
}
void init(){
for(auto &i:seg)i = -1;
return;
}
};
#undef ls
#undef rs
#undef mid
struct D{
int tp,id,pos;
D(){}
D(int tt,int ii,int pp):tp(tt),id(ii),pos(pp){}
bool operator<(D b)const{
return pos == b.pos?tp<b.tp:pos<b.pos;
}
};
SEG1 seg1;
SEG2 seg2;
pii req[mxn];
pii range[mxn];
int H[mxn];
int N,Q;
vector<D> op;
int ans[mxn];
void solve(){
op.clear();
seg1.init();
seg2.init();
for(int i = 1;i<=N;i++){
int pl = i+range[i].fs,pr = i+range[i].sc+1;
pl = min(pl,N),pr = min(pr,N+1);
op.push_back(D(1,i,pr));
op.push_back(D(2,i,pl));
op.push_back(D(3,i,i));
}
for(int i = 1;i<=Q;i++){
op.push_back(D(4,i,req[i].sc));
}
sort(op.begin(),op.end());
for(auto &[tp,id,___]:op){
//cout<<tp<<':'<<id<<' '<<___<<"::"<<seg1.seg[0].val<<endl;
if(tp == 1){
seg2.modify(0,0,N,id,seg1.getval(0,0,N,id,id).val);
seg1.chmin(0,0,N,id,inf);
}
else if(tp == 2){
seg1.chmin(0,0,N,id,H[id]);
}
else if(tp == 3){
int pl = id-range[id].sc,pr = id-range[id].fs;
pl = max(pl,0),pr = max(pr,0);
seg1.chmax(0,0,N,pl,pr,H[id]);
}
else{
ans[id] = max({ans[id],seg1.getval(0,0,N,req[id].fs,req[id].sc).val,seg2.getval(0,0,N,req[id].fs,req[id].sc)});
}
}
//cout<<endl;
return;
}
main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>N;
for(int i = 1;i<=N;i++){
cin>>H[i]>>range[i].fs>>range[i].sc;
}
cin>>Q;
for(int i = 1;i<=Q;i++){
cin>>req[i].fs>>req[i].sc;
}
memset(ans,-1,sizeof(ans));
solve();
reverse(H+1,H+N+1);
reverse(range+1,range+N+1);
for(int i = 1;i<=Q;i++){
req[i].fs = N+1-req[i].fs,req[i].sc = N+1-req[i].sc;
swap(req[i].fs,req[i].sc);
}
solve();
for(int i = 1;i<=Q;i++){
cout<<ans[i]<<'\n';
}
return 0;
}
Compilation message
antennas.cpp: In function 'void solve()':
antennas.cpp:158:17: error: no matching function for call to 'max(long long int&, int)'
158 | pl = max(pl,0),pr = max(pr,0);
| ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from antennas.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
254 | max(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: template argument deduction/substitution failed:
antennas.cpp:158:17: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
158 | pl = max(pl,0),pr = max(pr,0);
| ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from antennas.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
300 | max(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: template argument deduction/substitution failed:
antennas.cpp:158:17: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
158 | pl = max(pl,0),pr = max(pr,0);
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from antennas.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
3480 | max(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: template argument deduction/substitution failed:
antennas.cpp:158:17: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
158 | pl = max(pl,0),pr = max(pr,0);
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from antennas.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
3486 | max(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: template argument deduction/substitution failed:
antennas.cpp:158:17: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
158 | pl = max(pl,0),pr = max(pr,0);
| ^
antennas.cpp:158:32: error: no matching function for call to 'max(long long int&, int)'
158 | pl = max(pl,0),pr = max(pr,0);
| ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from antennas.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
254 | max(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: template argument deduction/substitution failed:
antennas.cpp:158:32: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
158 | pl = max(pl,0),pr = max(pr,0);
| ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from antennas.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
300 | max(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: template argument deduction/substitution failed:
antennas.cpp:158:32: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
158 | pl = max(pl,0),pr = max(pr,0);
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from antennas.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
3480 | max(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: template argument deduction/substitution failed:
antennas.cpp:158:32: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
158 | pl = max(pl,0),pr = max(pr,0);
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from antennas.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
3486 | max(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: template argument deduction/substitution failed:
antennas.cpp:158:32: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
158 | pl = max(pl,0),pr = max(pr,0);
| ^
antennas.cpp: At global scope:
antennas.cpp:169:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
169 | main(){
| ^~~~
