Submission #440209

#	Time	Username	Problem	Language	Result	Execution time	Memory
440209		leaked	Election (BOI18_election)	C++14	0 / 100	18 ms	26060 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 lwr[N];
int ans[N],x[N];
vec<pii>qry[N];
int mn[N][20];
int lvl[N];
vec<int>del[N];
bool is=0;
struct tr{
    int sm=0;
    int suf=2*N;
};
tr mg(tr a,tr b){
    tr c;
    c.sm=a.sm+b.sm;
    c.suf=min({b.suf,a.suf+b.sm});
   if(is) cout<<c.suf<<endl;
    return c;
}
tr emp,t[4*N];
void upd(int id,int x,int v,int tl,int tr){
    if(tl==tr){
        t[v].sm=x;t[v].suf=x;
        return;
    }
    int tm=(tl+tr)>>1;
    if(tm>=id) upd(id,x,2*v,tl,tm);
    else upd(id,x,2*v+1,tm+1,tr);
    t[v]=mg(t[2*v],t[2*v+1]);
}

tr get(int l,int r,int v,int tl,int tr){
    if(tl>=l && tr<=r) return t[v];
    if(tl>r || tr<l) return emp;
    int tm=(tl+tr)>>1;
    return mg(get(l,r,2*v,tl,tm),get(l,r,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);
        x[i]=(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();
            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[l].pb({r,i});
    }
    for(int i=0;i<=n;i++){
        if(x[i]<0)del[lwr[i]+2].pb(i);
    }
   // int x=0;
    for(int i=n;i>=1;i--){
        int w=(x[i]<0?0:1);
        upd(i,w,1,0,n);
        cout<<"APLY "<<i<<' '<<1<<endl;
        for(auto &z : qry[i]){

            int l=i,r=z.f;
            int answ=0;
            answ+=max(0,-(getmn(l,r)-a[l-1]));
           // cout<<get(l,r,1,0,n).suf<<endl;
            answ-=min(0,get(l,r,1,0,n).suf);
            ans[z.s]=answ;
        }
        for(auto &z : del[i]){
            upd(z,-1,1,0,n);
          // cout<<"APly "<<z<<' '<<-1<<endl;
        }
    }
    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