Submission #106278

#	Time	Username	Problem	Language	Result	Execution time	Memory
106278		RedNextCentury	Election (BOI18_election)	C++14	100 / 100	1368 ms	30216 KiB

election

#include<bits/stdc++.h>
using namespace std;
struct Q
{
    int l,r,id;
};
struct node
{
    int sum;
    int suf;
    node(){}
    node(int a,int b){sum=a,suf=b;}
};
node Merge(node a,node b)
{
    if (a.sum==1000000)return b;
    if (b.sum==1000000)return a;
    node ret;
    ret.sum=a.sum+b.sum;
    ret.suf = min(b.suf,b.sum+a.suf);
    return ret;
}
node tree[4000000];
int a[1000000];

#define mid (l+r)/2
#define L x*2
#define R x*2+1
void build(int x,int l,int r)
{
    if (l==r)
        tree[x]=node(a[l],min(a[l],0));
    else
    {
        build(L,l,mid);
        build(R,mid+1,r);
        tree[x]=Merge(tree[L],tree[R]);
    }
}
void upd(int x,int l,int r,int v,int val)
{
    if (v>r || v<l)return;
    if (l==r)
        tree[x]=node(val,min(val,0));
    else
    {
        upd(L,l,mid,v,val);
        upd(R,mid+1,r,v,val);
        tree[x]=Merge(tree[L],tree[R]);
    }
}
node query(int x,int l,int r,int s,int e)
{
    if (s>r || e<l)
        return node(1000000,0);
    if (l>=s && r<=e)
        return tree[x];
    return Merge(query(L,l,mid,s,e),query(R,mid+1,r,s,e));
}
bool operator<(Q a,Q b)
{
    return a.l>b.l;
}
Q q[1000000];
int ret[1000000];
int stk[1000000];
int sz=0;
int getLessThan(int v)
{
    int ret=sz;
    int l = 0, r=sz-1;
    while(l<=r)
    {
        if (stk[mid]<=v)
            ret=mid,r=mid-1;
        else
            l=mid+1;
    }
    return sz-ret;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    string s;
    cin>>s;
    for (int i=1;i<=n;i++)
    {
        if (s[i-1]=='C')a[i]=1;
        else a[i]=-1;
    }
    int m;
    cin>>m;
    for (int i=0;i<m;i++)
    {
        cin>>q[i].l>>q[i].r;
        q[i].id=i;
    }
    build(1,1,n);
    sort(q,q+m);
    int l=n+1;
    for (int i=0;i<m;i++)
    {
        while(l>q[i].l)
        {
            l--;
            if (a[l]==-1)
            {
                stk[sz++] = l;
                upd(1,1,n,l,0);
            }
            else if (sz>0)
            {
                upd(1,1,n,stk[--sz],-1);
            }
        }
        ret[q[i].id] = getLessThan(q[i].r) - query(1,1,n,q[i].l,q[i].r).suf;
    }
    for (int i=0;i<m;i++)
        cout<<ret[i]<<endl;
}

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