Submission #102092

#	Time	Username	Problem	Language	Result	Execution time	Memory
102092		LittleFlowers__	Two Antennas (JOI19_antennas)	C++14	100 / 100	1255 ms	63608 KiB

antennas

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N=200010,
          INF=1e9;
int n,q;
int h[N],a[N],b[N],l[N],r[N];

int ans[N];
int C[4*N],D[4*N],M[4*N];
vector<int> st[N],ed[N],qry[N];

void trans(int s){
    if(M[s]==INF) return;
    M[2*s]=min(M[2*s],M[s]);        M[2*s+1]=min(M[2*s+1],M[s]);
    D[2*s]=max(D[2*s],C[2*s]-M[s]); D[2*s+1]=max(D[2*s+1],C[2*s+1]-M[s]);
    M[s]=INF;
}
void upd(int s,int l,int r,int i){
    if(l>i||i>r) return;
    if(l==r){
        C[s]=(C[s]==-INF ? h[i] : -INF); return;
    }
    trans(s);
    int m=(l+r)/2;
    upd(2*s,l,m,i); upd(2*s+1,m+1,r,i);
    C[s]=max(C[2*s],C[2*s+1]);
}
void mod(int s,int l,int r,int u,int v,int x){
    if(l>v||u>r||C[s]==-INF) return;
    if(u<=l&&r<=v){
        M[s]=min(M[s],x); D[s]=max(D[s],C[s]-x); return;
    }
    trans(s);
    int m=(l+r)/2;
    mod(2*s,l,m,u,v,x); mod(2*s+1,m+1,r,u,v,x);
    D[s]=max(D[2*s],D[2*s+1]);
}
int que(int s,int l,int r,int u,int v){
    if(l>v||u>r) return -INF;
    if(u<=l&&r<=v){
        return D[s];
    }
    trans(s);
    int m=(l+r)/2;
    return max(que(2*s,l,m,u,v),que(2*s+1,m+1,r,u,v));
}
void solve(){
    for(int i=1;i<=n;++i){
        if(i+a[i]<=n) st[i+a[i]].push_back(i);
        if(i+b[i]<n)  ed[i+b[i]+1].push_back(i);
    }
    for(int i=1;i<=q;++i){
        qry[r[i]+1].push_back(i);
    }

    for(int i=1;i<=4*n;++i){
        C[i]=D[i]=M[i]=-INF; M[i]=-M[i];
    }
    for(int i=1;i<=n+1;++i){
        for(auto t:st[i])  upd(1,1,n,t);
        for(auto t:ed[i])  upd(1,1,n,t);
        for(auto t:qry[i]) ans[t]=max(ans[t],que(1,1,n,l[t],i-1));
        if(i-a[i]>0) mod(1,1,n,max(1ll,i-b[i]),i-a[i],h[i]);
    }
}
signed main(){
    ios_base::sync_with_stdio(false),cin.tie(nullptr);
    //freopen("ANTENNAS.inp","r",stdin);
    //freopen("ANTENNAS.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>>l[i]>>r[i];
    }

    fill(ans+1,ans+q+1,-1);

    solve();

    for(int i=1;i<=n+1;++i){
        st[i].clear(); ed[i].clear(); qry[i].clear();
    }
    reverse(h+1,h+n+1); reverse(a+1,a+n+1); reverse(b+1,b+n+1);
    for(int i=1;i<=q;++i){
        l[i]=n-l[i]+1; r[i]=n-r[i]+1; swap(l[i],r[i]);
    }

    solve();

    for(int i=1;i<=q;++i){
        cout<<ans[i]<<"\n";
    }
}

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