Submission #1150199

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150199		fatman87878	Two Antennas (JOI19_antennas)	C++20	100 / 100	385 ms	28312 KiB

antennas

#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define all(x) (x).begin(),(x).end()
#define ll long long

constexpr int maxN=2e5+5;

int n,q,tagflag[maxN],a[maxN],b[maxN],h[maxN],ans[maxN],tag[maxN];

vector<pair<int,int>> adj[maxN],qry[maxN];

struct NODE{
    int mx,a;
}segt[maxN<<1];

inline void upd(int pos,int tgw){
    segt[pos].a = max(segt[pos].a,segt[pos].mx-tgw);
    if(pos<n){
        tagflag[pos] = 1;
        tag[pos] = min(tag[pos],tgw);
    }
}

inline void push(int pos){
    pos+=n;
    for(int h = __lg(n);h;h--){
        int i = pos>>h;
        if(!i)continue;
        if(tagflag[i])upd(i<<1,tag[i]),upd(i<<1|1,tag[i]),tag[i] = 1e9+1,tagflag[i] = 0;
    }
}

inline void pull(int pos){
    for(pos+=n;pos>>=1;)if(!tagflag[pos]){
        segt[pos].mx = max(segt[pos<<1].mx,segt[pos<<1|1].mx);
        segt[pos].a = max(segt[pos<<1].a,segt[pos<<1|1].a);
    }
}

inline void mdf(int pos,int t){
    push(pos),segt[pos+n].mx = t,pull(pos);
}

inline void mdf2(int _l,int _r,int tgw){
    push(_l),push(_r-1);
    for(int l = _l+n,r = _r+n;l<r;l>>=1,r>>=1){
        if(l&1)upd(l++,tgw);
        if(r&1)upd(--r,tgw);
    }
    pull(_l),pull(_r-1);
}

inline int query(int l,int r){
    push(l),push(r-1);
    int ret = -1;
    for(l+=n,r+=n;l<r;l>>=1,r>>=1){
        if(l&1)ret = max(ret,segt[l++].a);
        if(r&1)ret = max(ret,segt[--r].a);
    }
    return ret;
}

inline void solve(){
    for(int i = 0;i<n;i++){
        tag[i] = 1e9+1;
        tagflag[i] = 0;
        segt[i+n] = {0,-1};
    }
    for(int i = n;--i;){
        segt[i] = {max(segt[i<<1].mx,segt[i<<1|1].mx),
                    max(segt[i<<1].a,segt[i<<1|1].a)};
    }
    for(int i = 0;i<n;i++){
        for(auto [a,b]:adj[i]){
            if(b==1)mdf(a,h[a]);
            else mdf(a,0);
        }
        mdf2(max(0,i-b[i]),max(0,i-a[i]+1),h[i]);
        for(auto [l,id]:qry[i])ans[id] = max(ans[id],query(l,i+1));
    }
}

int main(){
    IOS
    cin>>n;
    for(int i = 0;i<n;i++){
        cin>>h[i]>>a[i]>>b[i];
        adj[min(n,i+a[i])].emplace_back(i,1);
        adj[min(n,i+b[i]+1)].emplace_back(i,-1);
    }
    cin>>q;
    for(int i = 0;i<q;i++){
        int l,r;cin>>l>>r,--l,--r;
        qry[r].emplace_back(l,i);
    }
    fill(ans,ans+q,-1);
    solve();
    for(int i = 0;i<n;i++)h[i] = 1e9+1-h[i];
    solve();
    for(int i = 0;i<q;i++)cout<<ans[i]<<'\n';
}

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