# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
951610 | hengliao | Two Antennas (JOI19_antennas) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>
typedef long long ll;
const ll mxN=2e5+5;
const ll inf=1e18;
ll h[mxN];
ll a[mxN];
ll b[mxN];
ll n, q;
vll add[mxN];
vll minu[mxN];
struct segtree{
vll tree;
ll treelen;
void init(ll siz){
treelen=siz+1;
while(__builtin_popcountll(treelen)!=1){
treelen++;
}
tree=vll(2*treelen, 0);
}
void update(ll idx, ll val){
ll tar=treelen+idx;
tree[tar]=val;
tar/=2;
while(tar>0){
tree[tar]=max(tree[2*tar], tree[2*tar+1]);
tar/=2;
}
}
ll getmax(ll idx, ll low, ll high, ll qlow, ll qhigh){
if(low>=qlow && high<=qhigh){
return tree[idx];
}
if(low>qhigh || high<qlow){
return 0;
}
ll mid=(low+high)/2;
return max(getmax(2*idx, low, mid, qlow, qhigh),
getmax(2*idx+1, mid+1, high, qlow, qhigh));
}
};
struct segtree2{
vll tree;
ll treelen;
void init(ll siz){
treelen=siz+1;
while(__builtin_popcountll(treelen)!=1){
treelen++;
}
tree=vll(2*treelen, inf);
}
void update(ll idx, ll val){
ll tar=treelen+idx;
tree[tar]=val;
tar/=2;
while(tar>0){
tree[tar]=min(tree[2*tar], tree[2*tar+1]);
tar/=2;
}
}
ll getmin(ll idx, ll low, ll high, ll qlow, ll qhigh){
if(low>=qlow && high<=qhigh){
return tree[idx];
}
if(low>qhigh || high<qlow){
return inf;
}
ll mid=(low+high)/2;
return min(getmin(2*idx, low, mid, qlow, qhigh),
getmin(2*idx+1, mid+1, high, qlow, qhigh));
}
};
segtree seg1;
segtree2 seg2;
ll solve2(ll l, ll r){
seg1=vll(2*seg.treelen, 0);
seg2=vll(2*seg.treelen, inf);
/*for(auto it:seg2.tree){
cout<<it<<' ';
}
cout<<'\n';*/
for(ll i=l;i<=r;i++){
add[i].clear();
minu[i].clear();
}
ll re=-1;
for(ll i=l;i<=r;i++){
for(auto it:add[i]){
seg1.update(it, h[it]);
seg2.update(it, h[it]);
}
for(auto it:minu[i]){
seg1.update(it, 0);
seg2.update(it, inf);
}
if(i+a[i]<=r){
add[i+a[i]].pb(i);
}
if(i+b[i]+1<=r){
minu[i+b[i]+1].pb(i);
}
ll low=i-b[i], high=i-a[i];
low=max(low, l);
//cout<<i<<' '<<low<<' '<<high<<'\n';
if(high<low) continue;
ll mn=seg2.getmin(1, 0, seg2.treelen-1, low, high);
//cout<<mn<<'\n';
if(mn!=inf){
re=max(re, abs(h[i]-mn));
}
ll mx=seg1.getmax(1, 0, seg1.treelen-1, low, high);
//cout<<mx<<'\n';
if(mx!=0){
re=max(re, abs(h[i]-mx));
}
}
return re;
}
void solve(){
cin>>n;
for(ll i=0;i<n;i++){
cin>>h[i]>>a[i]>>b[i];
}
cin>>q;
for(ll i=0;i<q;i++){
ll l, r;
cin>>l>>r;
l--; r--;
cout<<solve2(l, r);
if(i<q-1) cout<<'\n';
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}