oj.uz

Submission #343899

# Submission time Handle Problem Language Result Execution time Memory
343899 2021-01-04T17:40:16 Z nicolaalexandra Election (BOI18_election) C++14
100 / 100
 1110 ms 50804 KB 
#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

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

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12140 KB Output is correct
2 Correct 10 ms 12268 KB Output is correct
3 Correct 10 ms 12268 KB Output is correct
4 Correct 10 ms 12268 KB Output is correct
5 Correct 10 ms 12268 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12140 KB Output is correct
2 Correct 10 ms 12268 KB Output is correct
3 Correct 10 ms 12268 KB Output is correct
4 Correct 10 ms 12268 KB Output is correct
5 Correct 10 ms 12268 KB Output is correct
6 Correct 112 ms 18540 KB Output is correct
7 Correct 99 ms 17952 KB Output is correct
8 Correct 104 ms 18156 KB Output is correct
9 Correct 107 ms 18436 KB Output is correct
10 Correct 108 ms 18412 KB Output is correct
11 Correct 122 ms 18668 KB Output is correct
12 Correct 112 ms 18536 KB Output is correct
13 Correct 112 ms 18668 KB Output is correct
14 Correct 109 ms 18652 KB Output is correct
15 Correct 105 ms 18540 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12140 KB Output is correct
2 Correct 10 ms 12268 KB Output is correct
3 Correct 10 ms 12268 KB Output is correct
4 Correct 10 ms 12268 KB Output is correct
5 Correct 10 ms 12268 KB Output is correct
6 Correct 112 ms 18540 KB Output is correct
7 Correct 99 ms 17952 KB Output is correct
8 Correct 104 ms 18156 KB Output is correct
9 Correct 107 ms 18436 KB Output is correct
10 Correct 108 ms 18412 KB Output is correct
11 Correct 122 ms 18668 KB Output is correct
12 Correct 112 ms 18536 KB Output is correct
13 Correct 112 ms 18668 KB Output is correct
14 Correct 109 ms 18652 KB Output is correct
15 Correct 105 ms 18540 KB Output is correct
16 Correct 972 ms 49260 KB Output is correct
17 Correct 815 ms 44976 KB Output is correct
18 Correct 872 ms 46316 KB Output is correct
19 Correct 837 ms 47804 KB Output is correct
20 Correct 966 ms 48236 KB Output is correct
21 Correct 1110 ms 50352 KB Output is correct
22 Correct 970 ms 50044 KB Output is correct
23 Correct 1066 ms 50804 KB Output is correct
24 Correct 915 ms 50028 KB Output is correct
25 Correct 870 ms 49300 KB Output is correct