Submission #1287363

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287363		ac_quan	Two Antennas (JOI19_antennas)	C++20	0 / 100	218 ms	40020 KiB

antennas

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
using namespace std;
const int N=200000+7;
struct Ev{int x; ll h; int t; Ev(int _x=0,ll _h=0,int _t=0):x(_x),h(_h),t(_t){}};
struct Qry{int l,r,id; bool operator<(const Qry& o) const{return r<o.r;}};
int n,m;
vector<Ev> ev[N];
int L[N],Rr[N]; ll H[N];
Qry q[N];
vector<ll> st_mn, st_mx, lz_mn, lz_mx; vector<ll> segans;
void build(int id,int l,int r){
    if((int)st_mn.size()==0) return;
    if(l==r){ st_mn[id]= (ll)4e18; st_mx[id]= -(ll)4e18; segans[id]=-1; lz_mn[id]=(ll)4e18; lz_mx[id]=-(ll)4e18; return;}
    int mid=(l+r)>>1;
    build(id<<1,l,mid); build(id<<1|1,mid+1,r);
    st_mn[id]=min(st_mn[id<<1],st_mn[id<<1|1]);
    st_mx[id]=max(st_mx[id<<1],st_mx[id<<1|1]);
    segans[id]=max(segans[id<<1],segans[id<<1|1]);
    lz_mn[id]=(ll)4e18; lz_mx[id]=-(ll)4e18;
}
inline void apply_lazy_to_node(int id,int l,int r,ll v_mn,ll v_mx){
    lz_mn[id]=min(lz_mn[id],v_mn);
    lz_mx[id]=max(lz_mx[id],v_mx);
    segans[id]=max(segans[id], max(lz_mx[id]-st_mn[id], st_mx[id]-lz_mn[id]));
}
void push(int id,int l,int r){
    if(lz_mn[id]!=(ll)4e18 || lz_mx[id]!=(ll)-4e18){
        int mid=(l+r)>>1;
        apply_lazy_to_node(id<<1,l,mid,lz_mn[id],lz_mx[id]);
        apply_lazy_to_node(id<<1|1,mid+1,r,lz_mn[id],lz_mx[id]);
        lz_mn[id]=(ll)4e18; lz_mx[id]=-(ll)4e18;
    }
}
void pull(int id){
    st_mn[id]=min(st_mn[id<<1],st_mn[id<<1|1]);
    st_mx[id]=max(st_mx[id<<1],st_mx[id<<1|1]);
    segans[id]=max(segans[id<<1],segans[id<<1|1]);
}
void update_point(int id,int l,int r,int pos,ll val){
    if(l>pos||r<pos) return;
    if(l==r){
        if(val<0){
            st_mn[id]=(ll)4e18;
            st_mx[id]=-(ll)4e18;
        } else {
            st_mn[id]=st_mx[id]=val;
        }
        lz_mn[id]=(ll)4e18; lz_mx[id]=-(ll)4e18;
        segans[id]=-1;
        return;
    }
    push(id,l,r);
    int mid=(l+r)>>1;
    update_point(id<<1,l,mid,pos,val);
    update_point(id<<1|1,mid+1,r,pos,val);
    pull(id);
}
void update_range(int id,int l,int r,int Lq,int Rq,ll val){
    if(l>Rq||r<Lq) return;
    if(l>=Lq && r<=Rq){
        apply_lazy_to_node(id,l,r,val,val);
        return;
    }
    push(id,l,r);
    int mid=(l+r)>>1;
    update_range(id<<1,l,mid,Lq,Rq,val);
    update_range(id<<1|1,mid+1,r,Lq,Rq,val);
    pull(id);
}
ll query(int id,int l,int r,int Lq,int Rq){
    if(l>Rq||r<Lq) return -1;
    if(l>=Lq && r<=Rq) return segans[id];
    push(id,l,r);
    int mid=(l+r)>>1;
    return max(query(id<<1,l,mid,Lq,Rq), query(id<<1|1,mid+1,r,Lq,Rq));
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>H[i]>>L[i]>>Rr[i];
    }
    for(int i=1;i<=n;i++){
        int li=i+L[i];
        int ri=i+Rr[i]+1;
        if(li<=n) ev[li].pb(Ev(i,H[i],1));
        if(ri<=n) ev[ri].pb(Ev(i,H[i],-1));
    }
    cin>>m;
    for(int i=1;i<=m;i++){cin>>q[i].l>>q[i].r; q[i].id=i;}
    sort(q+1,q+m+1);
    st_mn.assign(4*(n+5),(ll)4e18);
    st_mx.assign(4*(n+5),(ll)-4e18);
    lz_mn.assign(4*(n+5),(ll)4e18);
    lz_mx.assign(4*(n+5),(ll)-4e18);
    segans.assign(4*(n+5),-1);
    build(1,1,n);
    vector<ll> ans(m+2,-1);
    int cur=1;
    for(int i=1;i<=m;i++){
        while(cur<=q[i].r){
            for(auto &evv: ev[cur]){
                if(evv.t==1) update_point(1,1,n,evv.x,evv.h);
                else update_point(1,1,n,evv.x,-1);
            }
            int li = cur - Rr[cur];
            int ri = cur - L[cur];
            if(ri>=1){
                li = max(li,1);
                update_range(1,1,n,li,ri,H[cur]);
            }
            cur++;
        }
        ans[q[i].id]=query(1,1,n,q[i].l,q[i].r);
    }
    for(int i=1;i<=m;i++) cout<<ans[i]<<"\n";
    return 0;
}

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