Submission #926545

#	Time	Username	Problem	Language	Result	Execution time	Memory
926545		noyancanturk	Election (BOI18_election)	C++17	0 / 100	59 ms	96064 KiB

election

#ifndef Local
    #pragma GCC optimize("O3,unroll-loops")
    const int lim=5e5+5;
#else
    const int lim=3e3+3;
#endif
    
#include "bits/stdc++.h"
using namespace std;
    
#define int int64_t
#define pb push_back
    
const int mod=998244353;
//const int mod=(1ll<<61)-1;

using pii=pair<int,int>;

struct Node{
    int sum,pref,suf;
    inline Node():sum(0),pref(0),suf(0){}
    inline Node(int val):sum(val),pref(min<int>(0,val)),suf(pref){}
    inline Node(int sum,int pref,int suf):sum(sum),pref(pref),suf(suf){}
};

struct segtree{
    Node tree[4*lim];
    int n,*p;
    segtree(int n,int*p):n(n),p(p){
        build(1,n,1);
        //debug(1,n,1);
    }
    inline void debug(int l,int r,int node){
        cout<<"[ "<<l<<", "<<r<<" ] "<<tree[node].sum<<" "<<tree[node].pref<<" "<<tree[node].suf<<"\n";
        if(l^r){
            int mid=(l+r)>>1,child=node<<1;
            debug(l,mid,child),debug(mid+1,r,child|1);
        }
        if(node==1)cerr<<"\n";
    }
    inline Node merge(Node v1,Node v2){
        return Node(
            v1.sum+v2.sum,
            min(v1.pref,v1.sum+v2.pref),
            min(v2.suf,v2.sum+v1.suf)
        );
    }
    inline Node build(int l,int r,int node){
        if(l==r){
            return tree[node]=Node(p[l]);
        }
        int mid=(l+r)>>1,child=node<<1;
        return tree[node]=merge(build(l,mid,child),build(mid+1,r,child|1));
    }
    int P,VAL;
    inline void update(int l,int r,int node){
        if(l==r){
            tree[node]=Node(VAL);
            return;
        }
        int mid=(l+r)>>1,child=node<<1;
        if(P<=mid)update(l,mid,child);
        else update(mid+1,r,child|1);
        tree[node]=merge(tree[child],tree[child|1]);
        //cout<<"update: [ "<<l<<", "<<r<<" ] "<<tree[node].sum<<" "<<tree[node].pref<<" "<<tree[node].suf<<"\n";
    }
    inline void update(int p,int val){
        P=p,VAL=val;
        update(1,n,1);
    }
    int L,R;
    inline Node query(int l,int r,int node){
        if(L<=l&&r<=R){
            return tree[node];
        }
        if(r<L||R<l){
            return Node(0,INT_MAX,INT_MAX);
        }
        int mid=(l+r)>>1,child=node<<1;
        return merge(query(l,mid,child),query(mid+1,r,child|1));
    }
    inline int query(int l,int r){
        L=l,R=r;
        Node res=query(1,n,1);
        return max<int>(0,-res.suf);
    }
    int K;
    inline int firstneg(int l,int r,int node){
        //cout<<K<<"\n";
        //cout<<"[ "<<l<<", "<<r<<" ] "<<tree[node].sum<<" "<<tree[node].pref<<" "<<tree[node].suf<<"\n";
        if(l==r){
            return l;
        }
        int mid=(l+r)>>1,child=node<<1;
        if(tree[child].pref+K<0)return firstneg(l,mid,child);
        K+=tree[child].sum;
        return firstneg(mid+1,r,child|1);
    }
    inline int firstneg(){
        if(0<=tree[1].pref){
            return -1;
        }
        return firstneg(1,n,1);
    }
};

inline void solve(){
    int n;
    cin>>n;
    string s;
    cin>>s;
    int p[n+1];
    p[0]=0;
    for(int i=0;i<n;i++){
        p[i+1]=(s[i]=='C')?1:-1;
    }
    int q;
    cin>>q;
    vector<pii>a[n+1];
    for(int i=0;i<q;i++){
        int l,r;
        cin>>l>>r;
        a[l].pb(pii(r,i));
    }
    segtree st(n,p);
    deque<int>have;
    int to;
    while(~(to=st.firstneg())){
        have.pb(to);
        st.update(to,0);
    }
    int ans[q];
    for(int i=1;i<=n;i++){
        for(pii j:a[i]){
            int l=0,r=have.size()-1,aaa=0;
            while(l<=r){
                int mid=(l+r)>>1;
                if(have[mid]==j.first){
                    aaa=mid+1;
                    break;
                }else if(have[mid]<j.first){
                    l=aaa=mid+1;
                }else{
                    r=mid-1;
                }
            }
            ans[j.second]=aaa+st.query(i,j.first);
        }
        st.update(i,0);
        if(p[i]==1){
            if(~(to=st.firstneg())){
                have.push_front(to);
                st.update(to,0);
            }
        }else{
            assert(have.front()==i);
            have.pop_front();
        }
        /*
        for(int i:have)cout<<i<<" ";
        cout<<"\n";
        */
    }
    for(int i=0;i<q;i++){
        cout<<ans[i]<<"\n";
    }
}
    
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
#ifdef Local  
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#else
    
#endif
    int t=1;
    //cin>>t;
    while (t--)
    {
        solve();
    }
}

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