Submission #1190031

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190031		user736482	Modern Machine (JOI23_ho_t5)	C++20	100 / 100	2172 ms	231124 KiB

Main

#pragma GCC optimize("O3,unroll-loops,inline")
#pragma GCC target("avx2")
#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<<18)
#define INFL ((ll)INF*(ll)INF)
ll n,q,t,a,b,c,k,e,m,h,w,u,pier,sufsz,ak2=POT,ak3=POT;
vector<ll>kras,sufl={0},prefr={0};
vector<pair<pair<ll,ll>,pair<ll,ll>>>zap;
vector<pair<ll,ll>>vpom,nxt;
string s;
ll pierwszy[120007],smpref[120007],smsuf[120007],ans[120007],gdziel[120007],gdzier[120007];
vector<pair<pair<ll,ll>,ll>>sgtree[POT];
ll sg1[POT];
ll sg2[10000000],sg3[10000000];
ll lw2[10000000],pw2[10000000],lw3[10000000],pw3[10000000];
ll rot2[120007],rot3[120007];
void upd(ll v,ll val){
    sg1[v]=val;
    v/=2;
    while(v){
        sg1[v]=min(sg1[v*2],sg1[v*2+1]);
        v/=2;
    }
}
ll mn(ll pocz,ll kon,ll l,ll r,ll v){
    if(pocz>r || kon<l)return INFL;
    if(pocz<=l && kon>=r)return sg1[v];
    return min(mn(pocz,kon,l,(l+r)/2,v*2),mn(pocz,kon,(l+r)/2+1,r,v*2+1));
}
ll sm2(ll pocz,ll kon,ll l ,ll r,ll v){
    if(pocz>r || kon<l)return 0;
    if(pocz<=l && kon>=r)return sg2[v];
    return sm2(pocz,kon,l,(l+r)/2,lw2[v])+sm2(pocz,kon,(l+r)/2+1,r,pw2[v]);
}
ll sm3(ll pocz,ll kon,ll l ,ll r,ll v){
    if(pocz>r || kon<l)return 0;
    if(pocz<=l && kon>=r)return sg3[v];
    return sm3(pocz,kon,l,(l+r)/2,lw3[v])+sm3(pocz,kon,(l+r)/2+1,r,pw3[v]);
}

ll upd2(ll l,ll r,ll gdzie,ll v,ll val){
    if(l==r)sg2[ak2]=val;
    else{
        ll pom;
        if((l+r)/2>=gdzie){
        pom=upd2(l,(l+r)/2,gdzie,lw2[v],val);
        pw2[ak2]=pw2[v];
        lw2[ak2]=pom;
        }
        else{
        pom=upd2((l+r)/2+1,r,gdzie,pw2[v],val);
        lw2[ak2]=lw2[v];
        pw2[ak2]=pom;
        }
        sg2[ak2]=sg2[lw2[ak2]]+sg2[pw2[ak2]];
    }
    return ak2++;
}
ll upd3(ll l,ll r,ll gdzie,ll v,ll val){
    if(l==r)sg3[ak3]=val;
    else{
        ll pom;
        if((l+r)/2>=gdzie){
        pom=upd3(l,(l+r)/2,gdzie,lw3[v],val);
        pw3[ak3]=pw3[v];
        lw3[ak3]=pom;
        }
        else{
        pom=upd3((l+r)/2+1,r,gdzie,pw3[v],val);
        lw3[ak3]=lw3[v];
        pw3[ak3]=pom;
        }
        sg3[ak3]=sg3[lw3[ak3]]+sg3[pw3[ak3]];
    }
    return ak3++;
}
pair<ll,ll>operacja(ll x,ll pref,ll suf){
    x--;
    ll polewej=prefr[min(x,n-suf)]-prefr[min(pref,x)]+min(pref,x);
    ll poprawej=sufl[max(x+1,pref)]-sufl[n-min(suf,n-x-1)]+min(suf,n-x-1);
    if(polewej>=poprawej){
        ll pom;
        if(-prefr[pref]+prefr[min(x,n-suf)]>poprawej){
            pom=gdzier[1+prefr[min(x,n-suf)]-(poprawej-1)-1]+1;
        }
        else{
            if(pref>x){
                pom=x-poprawej;
            }
            else
            pom=(pref)-(poprawej-(prefr[min(x,n-suf)]-prefr[pref]));
        }
        return{min(pom,pref),n-pom};
    }    
    else{
        ll pom;
        polewej++;
        if(-sufl[n-suf]+sufl[1+max(x,pref-1)]>polewej){
            pom=gdziel[1+sufl[1+max(x,pref-1)]-(polewej-1)-1]-1;
        }
        else{
            if(suf>=n-x){
            pom=x+polewej;}
            else
            pom=n-suf-1+polewej+sufl[n-suf]-sufl[1+max(x,pref-1)];
        }
        return{pom+1,min(suf,n-pom-1)};
    }
}
ll brt(ll pref,ll suf,ll pocz,ll kon){
    if(pocz>kon){
        return pref+prefr[n-suf]-prefr[pref];
    }
    auto pom=operacja(kras[pocz],pref,suf);
    return brt(pom.ff,pom.ss,pocz+1,kon);
}
ll policz(ll ak,ll pocz,ll kon,ll l,ll r,ll v){
    if(kon<l || r<pocz)return ak;
    if(l>=pocz && r<=kon){
        return (ak+(*--lower_bound(sgtree[v].begin(),sgtree[v].end(),(pair<pair<ll,ll>,ll>){{ak,INF},INF})).ss)%(n+1);
    }
    ll pom=policz(ak,pocz,kon,l,(l+r)/2,v*2);
    return policz((pom),pocz,kon,(l+r)/2+1,r,v*2+1);
}
ll policzsmsuf(ll pref,ll l,ll r){
    return sm3(l+1,r,1,POT/2,rot3[n-pref]);
    ll rt=0;
    for(ll j=l;j<r;j++){
        if(kras[j]>pref){
            rt+=n-kras[j];
        }
    }
    return rt;
}
ll policzsmpref(ll pref,ll l,ll r){
    return sm2(l+1,r,1,POT/2,rot2[pref]);
    ll rt=0;
    for(ll j=l;j<r;j++){
        if(kras[j]<=pref){
            rt+=kras[j];
        }
    }
    return rt;
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    for(ll i=1;i<POT/2;i++){
        lw2[i]=i*2;
        pw2[i]=lw2[i]+1;
        lw3[i]=i*2;
        pw3[i]=lw3[i]+1;
    }
    rot2[0]=1;
    rot3[0]=1;
    vector<pair<ll,ll>>pomm;
    cin>>n>>m;
    cin>>s;
    pier=n;
    for(ll i=0;i<n;i++){
        if(s[i]=='R')s[i]='>';
        if(s[i]=='B')s[i]='<';
        prefr.pb(prefr.back());
        
        if(s[i]=='>'){
            prefr.back()++;
            gdzier[1+prefr.back()]=i;
        }
    }
    gdzier[1+0]=-1;
    gdzier[1+-1]=-INFL;
    for(ll i=n-1;i>=0;i--){
        sufl.pb(sufl.back());
        if(s[i]=='<'){
            sufl.back()++;
            gdziel[1+sufl.back()]=i;
        }
    }
    gdziel[1+-1]=INFL;
    gdziel[1+sufl.back()+1]=n;
    gdziel[1+0]=n;
    reverse(sufl.begin(),sufl.end());
    for(ll i=0;i<n;i++){
        
        if(s[i]=='<'){
            pier=i;
            break;
        }
    }
    sufsz=0;
    for(ll i=n-1;i>=0;i--){
        if(s[i]=='<'){
            sufsz++;
        }
        else break;
    }
    for(ll i=0;i<m;i++){
        cin>>a;
        pomm.pb({a,i});
        kras.pb(a);
    }
    pomm.pb({0,-1});
    pomm.pb({n+1,-1});
    sort(pomm.begin(),pomm.end());
    for(ll i=1;i<=m;i++){
        rot2[pomm[i].ff]=upd2(1,POT/2,1+pomm[i].ss,rot2[pomm[i-1].ff],pomm[i].ff);
    }
    for(ll i=1;i<=n;i++){
        rot2[i]=max(rot2[i],rot2[i-1]);
    }
    for(ll i=m;i>0;i--){
        rot3[n-pomm[i].ff+1]=upd3(1,POT/2,1+pomm[i].ss,rot3[n-pomm[i+1].ff+1],n-pomm[i].ff);
    }
    for(ll i=1;i<=n;i++){
        rot3[i]=max(rot3[i],rot3[i-1]);
    }
    for(ll i=0;i<m;i++){
        sgtree[i+POT/2].pb({{0,kras[i]-1},kras[i]+1});
        sgtree[i+POT/2].pb({{kras[i],n},kras[i]});
    }
    for(ll i=m;i<POT/2;i++){
        sgtree[i+POT/2].pb({{0,n},0});
    }
    for(ll i=POT/2-1;i>0;i--){
        vector<pair<pair<ll,ll>,ll>>v=sgtree[i*2],v2;
        if(i==1)break;
        for(ll j=0;j<v.size();j++){
            if((v[j].ff.ff+v[j].ss)%(n+1)<=(v[j].ff.ss+v[j].ss)%(n+1))
            v2.pb({{(v[j].ff.ff+v[j].ss)%(n+1),(v[j].ff.ss+v[j].ss)%(n+1)},v[j].ss%(n+1)});
            else{
                v2.pb({{(v[j].ff.ff+v[j].ss)%(n+1),n},v[j].ss%(n+1)});
                v2.pb({{0,(v[j].ff.ss+v[j].ss)%(n+1)},v[j].ss%(n+1)});
            }
        }
        sort(v2.begin(),v2.end());
        for(auto j : v2){
        }
        for(ll j=0;j<v2.size();j++){
            ll ak=lower_bound(sgtree[i*2+1].begin(),sgtree[i*2+1].end(),(pair<pair<ll,ll>,ll>){{v2[j].ff.ss,INF},INF})-sgtree[i*2+1].begin()-1;
            while(ak>=0 && sgtree[i*2+1][ak].ff.ss>=v2[j].ff.ff){
                sgtree[i].pb({{(max(v2[j].ff.ff,sgtree[i*2+1][ak].ff.ff)-v2[j].ss+n+1)%(n+1),(min(v2[j].ff.ss,sgtree[i*2+1][ak].ff.ss)-v2[j].ss+n+1)%(n+1)},(v2[j].ss+sgtree[i*2+1][ak].ss)%(n+1)});
                ak--;
            }
        }
        sort(sgtree[i].begin(),sgtree[i].end());
    }
    cin>>q;
    for(ll i=0;i<q;i++){
        ans[i]=-1;
        cin>>a>>b;
        a--;
        b--;
        zap.pb({{pier,sufsz},{a,b}});
        if(pier+sufsz!=n)
        vpom.pb({a,i});
        else
        ans[i]=policz(pier,a,b,0,POT/2-1,1);
    }
    while(vpom.size()){
        sort(vpom.begin(),vpom.end());
        reverse(vpom.begin(),vpom.end());
        ll nst=m-1;
        for(ll i=0;i<POT;i++)sg1[i]=INFL;
        for(pair<ll,ll> i : vpom){
            while(nst>=i.ff){
                upd(POT/2-1+kras[nst],nst);
                nst--;
            }
            auto ak=zap[i.ss];
            pierwszy[i.ss]=min(ak.ss.ss+1,mn(ak.ff.ff+1,n-ak.ff.ss,1,POT/2,1));
        }
        for(pair<ll,ll> i : vpom){
            auto ak=zap[i.ss];
            smpref[i.ss]=policzsmpref(ak.ff.ff,ak.ss.ff,pierwszy[i.ss]);
        }
        for(pair<ll,ll> i : vpom){
            auto ak=zap[i.ss];
            smsuf[i.ss]=policzsmsuf(ak.ff.ff,ak.ss.ff,pierwszy[i.ss]);
        }
        for(pair<ll,ll> i : vpom){
            auto ak=zap[i.ss];
            if(n-(gdzier[1+max(-1LL,prefr[max(-1LL,n-zap[i.ss].ff.ss)]-smsuf[i.ss])]+1)+(gdziel[1+max(-1LL,sufl[zap[i.ss].ff.ff]-smpref[i.ss])])>n){
                ll pocz=ak.ss.ff;
                ll kon=pierwszy[i.ss];
                while(pocz!=kon){
                    ll mid=(pocz+kon+1)/2;
                    auto ak=zap[i.ss];
                    smsuf[i.ss]=policzsmsuf(ak.ff.ff,ak.ss.ff,mid-1);
                    smpref[i.ss]=policzsmpref(ak.ff.ff,ak.ss.ff,mid-1);
                    if(n-(gdzier[1+max(-1LL,prefr[max(-1LL,n-zap[i.ss].ff.ss)]-smsuf[i.ss])]+1)+(gdziel[1+max(-1LL,sufl[zap[i.ss].ff.ff]-smpref[i.ss])])<=n){
                        pocz=mid;
                    }
                    else
                        kon=mid-1;
                }
                pierwszy[i.ss]=pocz-1;
                auto ak=zap[i.ss];
                    smsuf[i.ss]=policzsmsuf(ak.ff.ff,ak.ss.ff,pierwszy[i.ss]);
                    smpref[i.ss]=policzsmpref(ak.ff.ff,ak.ss.ff,pierwszy[i.ss]);
            }
            zap[i.ss].ff.ff=gdziel[1+max(-1LL,sufl[zap[i.ss].ff.ff]-smpref[i.ss])];
            zap[i.ss].ff.ss=n-(gdzier[1+max(-1LL,prefr[max(-1LL,n-zap[i.ss].ff.ss)]-smsuf[i.ss])]+1);
            if(pierwszy[i.ss]!=ak.ss.ss+1 && pierwszy[i.ss]>=ak.ss.ff){
               zap[i.ss].ff=operacja(kras[pierwszy[i.ss]],zap[i.ss].ff.ff,zap[i.ss].ff.ss);
            }
            zap[i.ss].ss.ff=pierwszy[i.ss]+1;
        }
        vpom.clear();
        for(ll i=0;i<q;i++){
            if(ans[i]!=-1)continue;
            if(zap[i].ss.ff>zap[i].ss.ss)   {
                ans[i]=brt(zap[i].ff.ff,zap[i].ff.ss,zap[i].ss.ff,zap[i].ss.ss);
                continue;
            }
            if(zap[i].ff.ff+zap[i].ff.ss==n){
                ans[i]=policz(zap[i].ff.ff,zap[i].ss.ff,zap[i].ss.ss,0,POT/2-1,1);
            }
            else{
                vpom.pb({zap[i].ss.ff,i});
            }
        }
    }
    for(ll i=0;i<q;i++)cout<<ans[i]<<"\n";
}

• Subtask 1: 3 / 3
• Subtask 2: 12 / 12
• Subtask 3: 10 / 10
• Subtask 4: 11 / 11
• Subtask 5: 26 / 26
• Subtask 6: 17 / 17
• Subtask 7: 21 / 21