Submission #343895

#	Time	Username	Problem	Language	Result	Execution time	Memory
343895		nicolaalexandra	Election (BOI18_election)	C++14	0 / 100	11 ms	12268 KiB

election

#include <bits/stdc++.h>
#define DIM 500010
#define INF 2000000000
using namespace std;

int v[DIM],ans[DIM],s[DIM];
char c[DIM];
int n,q,i,x,y,sol,sol2,sum,poz,k;

struct segment_tree{
    int sum,suf,poz;
} aint[DIM*4];

vector <pair <int,int> > qry[DIM];

void build (int nod, int st, int dr){
    if (st == dr){
        aint[nod].sum = aint[nod].suf = v[st];
        aint[nod].poz = st;
        return;
    }
    int mid = (st+dr)>>1;
    build (nod<<1,st,mid);
    build ((nod<<1)|1,mid+1,dr);

    int fiu_st = nod<<1, fiu_dr = (nod<<1)|1;
    aint[nod].sum = aint[fiu_st].sum + aint[fiu_dr].sum;

    if (aint[fiu_dr].suf <= aint[fiu_dr].sum + aint[fiu_st].suf){
        aint[nod].suf = aint[fiu_dr].suf;
        aint[nod].poz = aint[fiu_dr].poz;
    } else {
        aint[nod].suf = aint[fiu_dr].sum + aint[fiu_st].suf;
        aint[nod].poz = aint[fiu_st].poz;
    }

}

void query (int nod, int st, int dr, int x, int y){

    if (x <= st && dr <= y){
        if (sum + aint[nod].suf < sol){
            sol = sum + aint[nod].suf;
            poz = aint[nod].poz;
        }
        sum += aint[nod].sum;
        return;
    }

    int mid = (st+dr)>>1;
    if (y > mid)
        query ((nod<<1)|1,mid+1,dr,x,y);
    if (x <= mid)
        query (nod<<1,st,mid,x,y);
}

int main (){

    //ifstream cin ("election.in");
    //ofstream cout ("election.out");

    cin>>n>>c+1;

    for (i=1;i<=n;i++){
        if (c[i] == 'C')
            v[i] = 1;
        else v[i] = -1;
    }

    build (1,1,n);


    cin>>q;
    for (i=1;i<=q;i++){
        cin>>x>>y;
        qry[x].push_back(make_pair(y,i));

    }

    for (i=n;i;i--){
        if (v[i] == 1){
            if (k)
                k--;
        } else s[++k] = i;

        if (i == 1907)
            i = 1907;

        for (auto it : qry[i]){
            int y = it.first;

            sol = INF, sum = 0, poz = 0;
            query (1,1,n,i,y);

            if (sol >= 0){ /// sufixul minim e pozitiv
                ans[it.second] = k;
                continue;
            }

            /// caut binar cate elemente din stiva se afla in intervalul poz..y

            int st = 1, dr = k, sol_dr = 0, sol_st = k+1;
            while (st <= dr){
                int mid = (st+dr)>>1;
                if (s[mid] >= poz){
                    sol_dr = mid;
                    st = mid+1;
                } else dr = mid-1;
            }

            st = 1, dr = k;
            while (st <= dr){
                int mid = (st+dr)>>1;
                if (s[mid] <= y){
                    sol_st = mid;
                    dr = mid-1;
                } else st = mid+1;
            }

            if (sol_st <= sol_dr)
                ans[it.second] = k - sol_st + 1 + max(0,-sol - (sol_dr - sol_st + 1));
            else ans[it.second] = k - sol_st + 1 -sol;

        }
    }

    for (i=1;i<=q;i++)
        cout<<ans[i]<<"\n";

    return 0;
}

Compilation message (stderr)

election.cpp: In function 'int main()':
election.cpp:62:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |     cin>>n>>c+1;
      |             ~^~

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