Submission #1214148

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214148		user736482	Radio Towers (IOI22_towers)	C++20	100 / 100	1772 ms	974012 KiB

towers

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000009
#define INF 1000000019
#define POT (1<<20)
#define INFL 1000000000000000099
ll val[POT*15][5],lw[POT*15][5],pw[POT*15][5];//0 sum,1 min,2 min(na ujemnych)
ll ak[5];
ll h[100007][17];
ll p1[100007],p2[100007];
ll pop[100007],nxt[100007];
vector<pair<ll,ll>>root[3];// <moment,nowy root>
void st(ll cop,ll v,ll vl,ll idx,ll l,ll r,ll gdz){
    lw[v][idx]=lw[cop][idx];
    pw[v][idx]=pw[cop][idx];
    if((l+r)/2>=gdz){
        lw[v][idx]=ak[idx];
    }
    else pw[v][idx]=ak[idx];
    ak[idx]++;
    if(l==r){
        val[v][idx]=vl;
    }
    else{
        if((l+r)/2>=gdz)st(lw[cop][idx],lw[v][idx],vl,idx,l,(l+r)/2,gdz);
        else st(pw[cop][idx],pw[v][idx],vl,idx,(l+r)/2+1,r,gdz);
        if(idx)
        val[v][idx]=min(val[lw[v][idx]][idx],val[pw[v][idx]][idx]);
        else val[v][idx]=val[lw[v][idx]][idx]+val[pw[v][idx]][idx];
    }
}
ll get(ll v,ll l,ll r,ll pocz,ll kon,ll idx){
    if(pocz > r || kon < l)return idx*INFL;
    if(pocz<=l && kon>=r)return val[v][idx];
    if(idx)return min(get(lw[v][idx],l,(l+r)/2,pocz,kon,idx),get(pw[v][idx],(l+r)/2+1,r,pocz,kon,idx));
    else return get(lw[v][idx],l,(l+r)/2,pocz,kon,idx)+get(pw[v][idx],(l+r)/2+1,r,pocz,kon,idx);
}
ll mx(ll pocz,ll kon){
    if(pocz>kon)return 0;
    ll lg=log2(kon-pocz+1);
    return max(h[pocz][lg],h[kon-(1<<lg)+1][lg]);
}
void init(int n,vector<int>H){
    root[0].pb({INFL,0});
    root[1].pb({INFL,0});
    root[2].pb({INFL,0});
    ak[0]=20;ak[1]=20;ak[2]=20;ak[3]=20;ak[4]=20;
    for(ll i=0;i<n;i++)h[i][0]=H[i];
    for(ll i=0;i<20;i++){
        for(ll idx=0;i<5;i++){
            lw[i][idx]=i+1;
            pw[i][idx]=i+1;
        }
    }
    for(ll i=0;i<15*POT;i++){
        for(ll j=1;j<5;j++)val[i][j]=INFL;
    }
    stack<pair<ll,ll>>stt;
    stt.push({-1,-1});
    for(ll i=0;i<n;i++){
        while(h[i][0]<=stt.top().ff)stt.pop();
        pop[i]=stt.top().ss;
        stt.push({h[i][0],i});
    }
    while(stt.size()>1)stt.pop();
    stt.top().ss=n;
    for(ll i=n-1;i>=0;i--){
        while(h[i][0]<=stt.top().ff)stt.pop();
        nxt[i]=stt.top().ss;
        stt.push({h[i][0],i});
    }
    for(ll j=1;j<17;j++){
        for(ll i=0;i+(1<<j)<=n;i++)h[i][j]=max(h[i][j-1],h[i+(1<<(j-1))][j-1]);
    }
    vector<pair<ll,ll>>zd;//<czas,kto>
    for(ll i=0;i<n;i++){
        p1[i]=mx(pop[i]+1,i-1)-h[i][0];
        p2[i]=mx(i+1,nxt[i]-1)-h[i][0];
        zd.pb({min(p1[i],p2[i]),-i-INFL});
        if(p1[i]>p2[i]){
            zd.pb({p1[i],-i-1});
        }
        else zd.pb({p2[i],i});
    }
    sort(zd.begin(),zd.end());
    reverse(zd.begin(),zd.end());
    for(auto op :zd){
        if(op.ss<=-INFL){
            ll i=-op.ss-INFL;
            root[0].pb({op.ff,ak[0]});
            st(root[0][root[0].size()-2].ss,ak[0]++,1,0,1,POT/2,i+1);
            st(root[0][root[0].size()-2].ss,ak[3]++,i+1,3,1,POT/2,i+1);
            st(root[0][root[0].size()-2].ss,ak[4]++,-i-1,4,1,POT/2,i+1);
            if(p1[i]>p2[i]){
                root[1].pb({op.ff,ak[1]});
                st(root[1][root[1].size()-2].ss,ak[1]++,INFL,1,1,POT/2,i+1);
            }
            else{
                root[2].pb({op.ff,ak[2]});
                st(root[2][root[2].size()-2].ss,ak[2]++,INFL,2,1,POT/2,i+1);
            }
        }
        else if(op.ss<0){
            ll i=-op.ss-1;
            root[1].pb({op.ff,ak[1]});
            st(root[1][root[1].size()-2].ss,ak[1]++,-nxt[i]-1,1,1,POT/2,i+1);
        }
        else{
            ll i=op.ss;
            root[2].pb({op.ff,ak[2]});
            st(root[2][root[2].size()-2].ss,ak[2]++,pop[i]+1,2,1,POT/2,i+1);
        }
    }
    for(ll i=0;i<3;i++)reverse(root[i].begin(),root[i].end());
}
ll max_towers(int l,int r,int d){
    l++;
    r++;
    ll r0=(*lower_bound(root[0].begin(),root[0].end(),pair<ll,ll>{d,-INFL})).ss;
    ll r1=(*lower_bound(root[1].begin(),root[1].end(),pair<ll,ll>{d,-INFL})).ss;
    ll r2=(*lower_bound(root[2].begin(),root[2].end(),pair<ll,ll>{d,-INFL})).ss;
    ll ans=get(r0,1,POT/2,l,r,0);
    ll lew=get(r0,1,POT/2,l,r,3)-1;
    ll prw=-get(r0,1,POT/2,l,r,4)+1;
    if(ans==0){
        lew=r;
        prw=l;
    }
    if(-get(r1,1,POT/2,prw,r,1)>r)ans++;
    if(get(r2,1,POT/2,l,lew,2)<l)ans++;
    return max(ans,1LL);
}

• Subtask 1: 4 / 4
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 14 / 14
• Subtask 5: 17 / 17
• Subtask 6: 19 / 19
• Subtask 7: 23 / 23