oj.uz

Submission #114830

# Submission time Handle Problem Language Result Execution time Memory
114830 2019-06-03T11:22:00 Z Charis02 Election (BOI18_election) C++14
100 / 100
 1383 ms 48536 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 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.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 512 KB Output is correct
4 Correct 7 ms 512 KB Output is correct
5 Correct 6 ms 512 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 512 KB Output is correct
4 Correct 7 ms 512 KB Output is correct
5 Correct 6 ms 512 KB Output is correct
6 Correct 169 ms 8568 KB Output is correct
7 Correct 159 ms 8312 KB Output is correct
8 Correct 166 ms 8440 KB Output is correct
9 Correct 164 ms 8420 KB Output is correct
10 Correct 162 ms 8312 KB Output is correct
11 Correct 181 ms 8760 KB Output is correct
12 Correct 177 ms 8696 KB Output is correct
13 Correct 174 ms 8952 KB Output is correct
14 Correct 173 ms 8816 KB Output is correct
15 Correct 164 ms 8440 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 512 KB Output is correct
4 Correct 7 ms 512 KB Output is correct
5 Correct 6 ms 512 KB Output is correct
6 Correct 169 ms 8568 KB Output is correct
7 Correct 159 ms 8312 KB Output is correct
8 Correct 166 ms 8440 KB Output is correct
9 Correct 164 ms 8420 KB Output is correct
10 Correct 162 ms 8312 KB Output is correct
11 Correct 181 ms 8760 KB Output is correct
12 Correct 177 ms 8696 KB Output is correct
13 Correct 174 ms 8952 KB Output is correct
14 Correct 173 ms 8816 KB Output is correct
15 Correct 164 ms 8440 KB Output is correct
16 Correct 1333 ms 46072 KB Output is correct
17 Correct 1305 ms 45560 KB Output is correct
18 Correct 1315 ms 46072 KB Output is correct
19 Correct 1292 ms 45688 KB Output is correct
20 Correct 1324 ms 45220 KB Output is correct
21 Correct 1364 ms 47828 KB Output is correct
22 Correct 1308 ms 47172 KB Output is correct
23 Correct 1383 ms 48536 KB Output is correct
24 Correct 1306 ms 47388 KB Output is correct
25 Correct 1266 ms 46584 KB Output is correct