Submission #861940

#	Time	Username	Problem	Language	Result	Execution time	Memory
861940		winter0101	Two Antennas (JOI19_antennas)	C++17	100 / 100	446 ms	65956 KiB

antennas

#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
const int maxn=2e5+9;
int h[maxn],a[maxn],b[maxn];
vector<pii>ask[maxn];
long long ans[maxn];
const long long inf=1e9+7;
long long lazymin[maxn*4],lazymax[maxn*4],mn[maxn*4],mx[maxn*4],best[maxn*4];
void build(int id,int l,int r){
lazymin[id]=inf;
lazymax[id]=-inf;
mn[id]=inf;
mx[id]=-inf;
best[id]=-1;
if (l==r)return;
int mid=(l+r)/2;
build(id*2,l,mid);
build(id*2+1,mid+1,r);
}
void push(int id){
if (lazymin[id]<inf){
lazymin[id*2]=min(lazymin[id*2],lazymin[id]);
lazymin[id*2+1]=min(lazymin[id*2+1],lazymin[id]);
lazymin[id]=inf;
}
if (lazymax[id]>-inf){
lazymax[id*2]=max(lazymax[id*2],lazymax[id]);
lazymax[id*2+1]=max(lazymax[id*2+1],lazymax[id]);
lazymax[id]=-inf;
}
best[id*2]=max({best[id*2],lazymax[id*2]-mn[id*2],mx[id*2]-lazymin[id*2]});
best[id*2+1]=max({best[id*2+1],lazymax[id*2+1]-mn[id*2+1],mx[id*2+1]-lazymin[id*2+1]});
}
void updatepoint(int id,int l,int r,int u,int val1,int val2){
if (l>u||r<u){
return;
}
if (l==r){
best[id]=max({best[id],-mn[id]+lazymax[id],-lazymin[id]+mx[id]});
lazymin[id]=1e9+7;
lazymax[id]=-1e9+7;
mn[id]=val1;
mx[id]=val2;
return;
}
push(id);
int mid=(l+r)/2;
updatepoint(id*2,l,mid,u,val1,val2);
updatepoint(id*2+1,mid+1,r,u,val1,val2);
best[id]=max({best[id],best[id*2],best[id*2+1]});
mn[id]=min(mn[id*2],mn[id*2+1]);
mx[id]=max(mx[id*2],mx[id*2+1]);
}
void updaterange(int id,int l,int r,int u,int v,long long val){
if (l>v||r<u||u>v)return;
if (u<=l&&r<=v){
lazymax[id]=max(lazymax[id],val);
lazymin[id]=min(lazymin[id],val);
best[id]=max({best[id],-mn[id]+lazymax[id],-lazymin[id]+mx[id]});
return;
}
int mid=(l+r)/2;
push(id);
updaterange(id*2,l,mid,u,v,val);
updaterange(id*2+1,mid+1,r,u,v,val);
best[id]=max({best[id],best[id*2],best[id*2+1]});
}
long long get(int id,int l,int r,int u,int v){
if (l>v||r<u||u>v)return -1;
if (u<=l&&r<=v)return best[id];
int mid=(l+r)/2;
push(id);
return max(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
}
vector<int>add[maxn];
vector<int>del[maxn];
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen("temp.OUT","w",stdout);
    int n;
    cin>>n;
    for1(i,1,n)cin>>h[i]>>a[i]>>b[i];
    int q;
    cin>>q;
    for1(i,1,q){
    int l,r;
    cin>>l>>r;
    ask[r].pb({l,i});
    ans[i]=-1;
    }
    for1(i,1,n){
    if (i+a[i]<=n){
    add[i+a[i]].pb(i);
    }
    if (i+b[i]<=n){
    del[i+b[i]+1].pb(i);
    }
    }
    build(1,1,n);
    for1(i,1,n){
    for (auto v:add[i]){
    updatepoint(1,1,n,v,h[v],h[v]);
    }
    for (auto v:del[i]){
    updatepoint(1,1,n,v,inf,-inf);
    }
    int l=max(1,i-b[i]),r=i-a[i];
    if (l<=r){
    updaterange(1,1,n,l,r,h[i]);
    }
    for (auto v:ask[i]){
    ans[v.se]=get(1,1,n,v.fi,i);
    }
    }
    for1(i,1,q)cout<<ans[i]<<'\n';
}

• Subtask 1: 2 / 2
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 65 / 65