Submission #343899

#	Time	Username	Problem	Language	Result	Execution time	Memory
343899		nicolaalexandra	Election (BOI18_election)	C++14	100 / 100	1110 ms	50804 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 update (int nod, int st, int dr, int poz, int val){
    if (st == dr){
        aint[nod].sum = aint[nod].suf = val;
        return;
    }
    int mid = (st+dr)>>1;
    if (poz <= mid)
        update (nod<<1,st,mid,poz,val);
    else update ((nod<<1)|1,mid+1,dr,poz,val);

    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){
                update (1,1,n,s[k],v[s[k]]);
                k--;
            }
        } else {
            s[++k] = i;
            update (1,1,n,i,0);
        }

        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,it.first);

            /// primul mai mic sau egal cu y din stiva
            int st = 1, dr = k, sol_st = k+1;
            while (st <= dr){
                int mid = (st+dr)>>1;
                if (s[mid] <= y){
                    sol_st = mid;
                    dr = mid-1;
                } else st = mid+1;
            }

            ans[it.second] = k - sol_st + 1 + max(0,-sol);
        }
    }

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

    return 0;
}

Compilation message (stderr)

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

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