Submission #440051

#	Time	Username	Problem	Language	Result	Execution time	Memory
440051		leaked	Election (BOI18_election)	C++14	0 / 100	18 ms	22172 KiB

election

#include <bits/stdc++.h>

#define vec vector
#define f first
#define s second
#define endl '\n'
#define pb push_back
#define sz(x) (int)x.size()

using namespace std;
typedef pair<int,int> pii;
const int N=5e5+1;
int lft[N],rgt[N];///for mx
int lwr[N];
int ans[N];
vec<pii>qry[N];
int mn[N][20];
int lvl[N];
int t[4*N],p1[4*N],p2[4*N];
void apply(int v,int x){
    t[v]=x;p1[v]=x;p2[v]=0;
}
void add(int v,int x){
    t[v]+=x;
    if(p1[v]!=2e9){
        p1[v]+=x;
    }
    else{
        p2[v]+=x;
    }
}
void push(int v,int tl,int tr){
    if(tl==tr) return;
    if(p1[v]!=2e9){
        for(auto &u : {2*v,2*v+1}){
            apply(u,p1[v]);
        }
        p1[v]=2e9;
    }
    if(p2[v]){
        for(auto &u : {2*v,2*v+1}){
            add(u,p2[v]);
        }
        p2[v]=0;
    }
}
void upd(int l,int r,int t,int x,int v,int tl,int tr){
    if(tl>=l && tr<=r){
        if(t==0)apply(v,x);
        else add(v,x);
        return;
    }
    if(tl>r || tr<l) return;
    push(v,tl,tr);
    int tm=(tl+tr)>>1;
    upd(l,r,t,x,2*v,tl,tm);upd(l,r,t,x,2*v+1,tm+1,tr);
}
int get(int id,int v,int tl,int tr){
    if(tl==tr) return t[v];
    int tm=(tl+tr)>>1;
    push(v,tl,tr);
    if(tm>=id) return get(id,2*v,tl,tm);
    else return get(id,2*v+1,tm+1,tr);
}
int getmn(int l,int r){
    int x=lvl[r-l+1];
    return min(mn[l][x],mn[r-(1<<x)+1][x]);
}
signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,q;
    cin>>n;
    vec<int>a(n+1);string s;
    cin>>s;s.insert(s.begin(),'0');
    for(int i=1;i<=n;i++){
        a[i]=(i?a[i-1]:0)+(s[i]=='C'?1:-1);
        mn[i][0]=a[i];
    }
    for(int i=2;i<N;i++) lvl[i]=lvl[i/2]+1;
    for(int j=1;j<20;j++){
        for(int i=0;i+(1<<(j-1))<=n;i++){
            mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
            //cout<<i<<' '<<j<<' '<<mn[i][j]<<endl;
        }
    }
    vec<pii>vc;
    {
        vc.pb({2e9,-1});
        for(int i=0;i<=n;i++){
            while(sz(vc) && vc.back().f<=a[i]) vc.pop_back();
            lft[i]=vc.back().s;
            vc.pb({a[i],i});
        }
    }
    vc.clear();
    {
        vc.pb({2e9,n+1});
        for(int i=n;i>=0;i--){
            while(sz(vc) && vc.back().f<a[i]) vc.pop_back();
            rgt[i]=vc.back().s;
            vc.pb({a[i],i});
        }
    }
    vc.clear();
    {
        vc.pb({-2e9,-1});
        for(int i=0;i<=n;i++){
            while(sz(vc) && vc.back().f>a[i]) vc.pop_back();
            lwr[i]=vc.back().s;
            vc.pb({a[i],i});
        }
    }
    cin>>q;
    for(int i=0;i<q;i++){
        int l,r;
        cin>>l>>r;
        qry[r].pb({l,i});
    }
    fill(p1,p1+4*N,2e9);
    for(int i=0;i<=n;i++){
        ///i need maximum right such that pref[i-1]>pref[r]
       upd(lft[i]+1,i,0,a[i],1,0,n);
       // cout<<"APPLY "<<lft[i]+2<<' '<<i+1<<' '<<a[i]<<endl;
        /// i'm in it if l<=i and pref[i]-pref[l-1]<0 lwr[i]>=l(maybe)
        upd(lwr[i]+2,i,1,-1,1,0,n);
        //cout<<"ADD "<<lwr[i]+1<<' '<<i-1<<' '<<-1<<endl;
       
        for(auto &z : qry[i]){
            int l=z.f,r=i;
            int answ=0;
            answ+=max(0,-(getmn(l,r)-a[l-1]));
            //cout<<"MN "<<getmn(l,r)<<' '<<a[l-1]<<endl;
            answ-=min(0,a[r]-get(l,1,0,n));
            
            ans[z.s]=answ;
        }
    }
    for(int i=0;i<q;i++) cout<<ans[i]<<endl;
    return 0;
}

• Subtask 1: 0 / 28
• Subtask 2: 0 / 54
• Subtask 3: 0 / 18