Submission #465326

#	Time	Username	Problem	Language	Result	Execution time	Memory
465326		hina_in_sky	Election (BOI18_election)	C++14	0 / 100	2 ms	460 KiB

election

#include<bits/stdc++.h>
#include<vector>
using namespace std;
#define int long long
#define pb push_back
#define Good_Bye_amano_hina cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
typedef long long ll;
typedef unsigned long long ull;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn=1000005;
ll t,n,cnt,x,m,a[maxn],b[4*maxn],bb[4*maxn],ans,pos,l,r,y,tag[4*maxn],mn,k,mod=1000000007,pre[500005],suf[500005],max1,max2;
string s;
vector<int> v[30];
ll fpow(ll x,ll y)
{
    if(y==0)
    {
        return 1%mod;
    }
    ll a=x%mod;
    ll a2=1%mod;
    while(y>1)
    {
        if(y%2)
        {
            a2*=a;
            a2%=mod;
        }
        a*=a;
        a%=mod;
        y/=2;
    }
    return (a*a2)%mod;
}
void build(ll l,ll r,ll v)
{
    if(l==r)
    {
        b[v]=pre[l];
        return;
    }
    ll mid=(l+r)/2;
    build(l,mid,2*v+1);
    build(mid+1,r,2*v+2);
    b[v]=min(b[2*v+1],b[2*v+2]);
}
ll qu(ll l, ll r, ll v, ll l2, ll r2)
{
    if(l==l2&&r==r2)
    {
        return b[v];
    }
    // push
    ll mid=(l+r)/2;
    /*b[2*v+1]+=(mid-l+1)*tag[v];
    b[2*v+2]+=(r-mid)*tag[v];
    tag[2*v+1]+=tag[v];
    tag[2*v+2]+=tag[v];
    tag[v]=0;*/
    if(mid>=r2)
    {
        return qu(l,mid,2*v+1,l2,r2);
    }
    else if(mid+1<=l2)
    {
        return qu(mid+1,r,2*v+2,l2,r2);
    }
    else
    {
        return min(qu(l,mid,2*v+1,l2,mid),qu(mid+1,r,2*v+2,mid+1,r2));
    }
}
void build2(ll l,ll r,ll v)
{
    if(l==r)
    {
        bb[v]=suf[l];
        return;
    }
    ll mid=(l+r)/2;
    build2(l,mid,2*v+1);
    build2(mid+1,r,2*v+2);
    bb[v]=min(bb[2*v+1],bb[2*v+2]);
}
ll qu2(ll l, ll r, ll v, ll l2, ll r2)
{
    if(l==l2&&r==r2)
    {
        return bb[v];
    }
    // push
    ll mid=(l+r)/2;
    /*b[2*v+1]+=(mid-l+1)*tag[v];
    b[2*v+2]+=(r-mid)*tag[v];
    tag[2*v+1]+=tag[v];
    tag[2*v+2]+=tag[v];
    tag[v]=0;*/
    if(mid>=r2)
    {
        return qu2(l,mid,2*v+1,l2,r2);
    }
    else if(mid+1<=l2)
    {
        return qu2(mid+1,r,2*v+2,l2,r2);
    }
    else
    {
        return min(qu2(l,mid,2*v+1,l2,mid),qu2(mid+1,r,2*v+2,mid+1,r2));
    }
}
/*void modify(ll l, ll r, ll v, ll l2, ll r2, ll m)
{
    if(l==l2&&r==r2)
    {
        //tag[v]+=m;
        b[v]+=(r-l+1)*m;
        return;
    }
    ll mid=(l+r)/2;
    // push
    b[2*v+1]+=(mid-l+1)*tag[v];
    b[2*v+2]+=(r-mid)*tag[v];
    tag[2*v+1]+=tag[v];
    tag[2*v+2]+=tag[v];
    tag[v]=0;
    if(mid>=r2)
    {
        modify(l,mid,2*v+1,l2,r2,m);
    }
    else if(mid+1<=l2)
    {
        modify(mid+1,r,2*v+2,l2,r2,m);
    }
    else
    {
        modify(l,mid,2*v+1,l2,mid,m);
        modify(mid+1,r,2*v+2,mid+1,r2,m);
    }
    b[v]=b[2*v+1]+b[2*v+2];
}*/
signed main()
{
    //freopen("output.txt", "r", stdin);
    Good_Bye_amano_hina
    // memorize a pair
    //cout<<fixed<<setprecision(20);
    cin>>n;
    cin>>s;
    pre[0]=0;
    for(int i=0;i<n;i++)
    {
        if(s[i]=='C')
        {
            pre[i+1]=pre[i]+1;
        }
        else
        {
            pre[i+1]=pre[i]-1;
        }
    }
    suf[n+1]=0;
    for(int i=n-1;i>=0;i--)
    {
        if(s[i]=='C')
        {
            suf[i+1]=suf[i+2]+1;
        }
        else
        {
            suf[i+1]=suf[i+2]-1;
        }
    }
    build(1,n,0);
    build2(1,n,0);
    cin>>t;
    while(t--)
    {
        cin>>l>>r;
        x=qu(1,n,0,l,r);
        max1=max(0LL,pre[l-1]-x);
        x=qu2(1,n,0,l,r);
        max2=max(0LL,suf[r+1]-x);
        cout<<max(max1,max2)<<'\n';

    }








}

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