oj.uz

Submission #114828

# Submission time Handle Problem Language Result Execution time Memory
114828 2019-06-03T11:11:39 Z Charis02 Election (BOI18_election) C++14
0 / 100
 6 ms 512 KB 
#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 300004
#define INF 1e9+7

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 = v.size();

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

        if(v[mid] > j)
        {
            high = mid-1;
            posa = min(posa,mid);
        }
        else
        {
            low = mid+1;
        }
    }

   // cout << i << " " << j << " " << posa << " " << query(0,n-1,0,i,j).sum << " " << query(0,n-1,0,i,j).res<<endl;

    ans[ind] = 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
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -