oj.uz

Submission #343852

# Submission time Handle Problem Language Result Execution time Memory
343852 2021-01-04T15:04:17 Z nicolaalexandra Election (BOI18_election) C++14
0 / 100
 7 ms 492 KB 
#include <bits/stdc++.h>
#define DIM 500010
#define INF 2000000000
using namespace std;

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

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

void build (int nod, int st, int dr){
    if (st == dr){
        aint[nod].sum = aint[nod].pref = aint[nod].suf = v[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;
    aint[nod].pref = min (aint[fiu_st].pref,aint[fiu_st].sum + aint[fiu_dr].pref);
    aint[nod].suf = min (aint[fiu_dr].suf, aint[fiu_dr].sum + aint[fiu_st].suf);

}

void query (int nod, int st, int dr, int x, int y){
    if (x <= st && dr <= y){
        sol = min (sol,sum + aint[nod].pref);
        sum += aint[nod].sum;
        return;
    }
    int mid = (st+dr)>>1;
    if (x <= mid)
        query (nod<<1,st,mid,x,y);
    if (y > mid)
        query ((nod<<1)|1,mid+1,dr,x,y);
}

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

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

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

int main (){

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

    cin>>n>>s+1;

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

    build (1,1,n);

    cin>>q;
    for (;q--;){
        cin>>x>>y;
        sum = 0, sol = INF;
        query (1,1,n,x,y);

        sum = 0, sol2 = INF;
        query2 (1,1,n,x,y);

        cout<<max(-min(sol,sol2),0)<<"\n";
    }

    return 0;
}

Compilation message

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

Subtask #1
0 / 28.0

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

Subtask #2
0 / 54.0

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

Subtask #3
0 / 18.0

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