Submission #114830

#	Time	Username	Problem	Language	Result	Execution time	Memory
114830		Charis02	Election (BOI18_election)	C++14	100 / 100	1383 ms	48536 KiB

election

#include<iostream>
#include<stdio.h>
#include<vector>
#include<cmath>
#include<queue>
#include<string.h>
#include<map>
#include<set>
#include<algorithm>
#define ll long long
#define pi pair < ll,ll >
#define mp(a,b) make_pair(a,b)
#define rep(i,a,b) for(int i = a;i < b;i++)
#define N 500004

using namespace std;

struct node{
    ll sum;
    ll res;
};

ll n,q,ar[N],l,r;
char c;
node seg[4*N];
pair < pi,ll > queries[N];
ll ans[N];
vector < ll > v;

void update(ll low,ll high,ll pos,ll slow,ll val)
{
    if(low == high && low == slow)
    {
        seg[pos].res = min(0LL,val);
        seg[pos].sum = val;
        return;
    }
    if(low > slow || high < slow)
        return;

    ll mid = (low + high)/2;

    update(low,mid,pos*2+1,slow,val);
    update(mid+1,high,pos*2+2,slow,val);

    seg[pos].res = min(seg[pos*2+2].res,seg[pos*2+2].sum + seg[pos*2+1].res);
    seg[pos].sum = seg[pos*2+1].sum+seg[pos*2+2].sum;
    return;
}

node query(ll low,ll high,ll pos,ll slow,ll shigh)
{
    if(low >= slow && high <= shigh)
    {
        return seg[pos];
    }
    if(low > shigh || high < slow)
    {
        node nu;
        nu.res = 0;
        nu.sum = 0;
        return nu;
    }

    ll mid = (low + high)/2;

    node q1 = query(low,mid,pos*2+1,slow,shigh);
    node q2 = query(mid+1,high,pos*2+2,slow,shigh);

    node ret;
    ret.res=  min(q2.res,q1.res+q2.sum);
    ret.sum = q1.sum+q2.sum;
    return ret;
}

void solve(ll i,ll j,ll ind)
{
    ll low = 0;
    ll high = v.size()-1;
    ll posa = -1;

    while(low <= high)
    {
        ll mid = (low + high)/2;

        if(v[mid] > j)
        {
            low = mid+1;
            posa = max(posa,mid);
        }
        else
        {
            high=mid-1;
        }
    }
/*
    rep(i,0,v.size())
    cout << v[i] << " ";
    cout << "   ";

    cout << i << " " << j << " " << posa << " " << query(0,n-1,0,i,j).sum << " " << query(0,n-1,0,i,j).res<<endl;
*/
    ans[ind] = v.size()-1-posa-query(0,n-1,0,i,j).res;
    return;
}

int main()
{
    ios_base::sync_with_stdio(false);

    cin >> n;

    rep(i,0,n)
    {
        cin >> c;

        if(c == 'C')
            ar[i] = 1;
        else
            ar[i] = -1;

        update(0,n-1,0,i,ar[i]);
    }

    cin >> q;

    rep(i,0,q)
    {
        cin >> l >> r;
        queries[i].first.first = l-1;
        queries[i].first.second = r-1;
        queries[i].second = i;
    }

    sort(queries,queries+q);

    ll cur = q-1;

    for(int i = n-1;i >= 0;i--)
    {
        if(ar[i] == -1)
        {
            update(0,n-1,0,i,0);
            v.push_back(i);
        }
        else if(!v.empty())
        {
            update(0,n-1,0,v[v.size()-1],-1);
            v.pop_back();
        }

        while(cur >= 0 && queries[cur].first.first == i)
        {
            solve(i,queries[cur].first.second,queries[cur].second);
            cur--;
        }
    }

    rep(i,0,q)
    {
        cout << ans[i] << endl;
    }

    return 0;
}

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