Submission #1181940

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181940		user736482	Modern Machine (JOI23_ho_t5)	C++20	37 / 100	722 ms	109572 KiB

Main

#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<<18)
#define INFL 100000000099

ll n,q,t,a,b,c,ans,k,e,m,h,w,u,pier;
vector<ll>kras;
string s;

vector<pair<pair<ll,ll>,ll>>sgtree[POT];

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);
    //cout<<pom<<" "<<l<<" "<<r<<" "<<v<<" "<<pocz<<" "<<kon<<"\n";
    return policz((pom),pocz,kon,(l+r)/2+1,r,v*2+1);
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    cin>>s;
    pier=n;
    for(ll i=0;i<n;i++){
        if(s[i]=='B'){
            pier=i;
            break;
        }
    }
    for(ll i=0;i<m;i++){
        cin>>a;
        kras.pb(a);
    }
    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]});
        //sgtree[i+POT/2].pb({{n,n},a});
    }
    for(ll i=m;i<POT/2;i++){
        sgtree[i+POT/2].pb({{0,n},0});
    }
    //return 0;
    for(ll i=POT/2-1;i>0;i--){
        //ll ak=0;
        vector<pair<pair<ll,ll>,ll>>v=sgtree[i*2],v2;
        if(i==1)break;
        //v2.pb({{0,v.back().ss-1},v.back().ss});
        
        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());
        //cout<<i<<": ";
        for(auto j : v2){
      //      cout<<j.ff.ff<<" "<<j.ff.ss<<" "<<j.ss<<"  ";
        }
      //  cout<<"\n";
        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){
        //        cout<<j<<" "<<ak<<"   ";
                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--;
            }
        }
       // cout<<"\n";
        sort(sgtree[i].begin(),sgtree[i].end());
        //ll ak2=0;
        
    }
    for(ll i=1;i<POT;i++){
        //for(auto j :sgtree[i])
       //     cout<<j.ff.ff<<" "<<j.ff.ss<<" "<<j.ss<<"   ";
      //  cout<<"\n";
    }//return 0;
    cin>>q;
    for(ll i=0;i<q;i++){
        cin>>a>>b;
        a--;
        b--;
        cout<<policz(pier,a,b,0,POT/2-1,1)<<"\n";
    }
}

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