Submission #69544

#	Time	Username	Problem	Language	Result	Execution time	Memory
69544		3zp	Election (BOI18_election)	C++14	100 / 100	1747 ms	136324 KiB

election

#include<bits/stdc++.h>
using namespace std;
struct vale{
    int S, mir, mal, ans;
};
 vale Z,  BL;
vale CO(vale X, vale Y){

    if(X.ans == 1e9) return Y;
    if(Y.ans == 1e9) return X;
    Z.S = X.S+ Y.S;
    Z.mir = min(Y.mir + X.S, X.mir);
    Z.mal = max(X.mal, Y.mal + X.S);
    Z.ans = max(X.ans, Y.ans);
    Z.ans = max(Z.ans, Y.mal + X.S - X.mir);
    return Z;
}
struct NODE{
    vale VAL;
    NODE *L, *R;
    void upd(){
        this->VAL = CO(this->L->VAL, this->R->VAL);
    }
};
int s[500009];
void build(NODE *&x, int l, int r){
    x = new NODE();
    if(l == r){
        int k =  s[l] - s[l-1];
        x->VAL.S = k;
        x->VAL.mir = min(0, k);
        x->VAL.mal = max(0, k);
        x->VAL.ans = max(k, 0);
    }
    else{
        int mid = (l + r)/2;
        build(x->L, l, mid);
        build(x->R, mid+1, r);
        x->upd();
    }
 }

vale cnt(NODE *&x, int l, int r, int a, int b){

    if(a > r || b < l) { return BL;}
    if(l >= a && r <= b) {return x->VAL;}
    int mid = (l + r)/2;
    return CO(cnt(x->L, l, mid, a ,b),cnt(x->R, mid+1, r, a, b));
}
NODE *rt, *ANS;
main(){
    BL .ans = 1e9;
    int n;
    cin >> n;
    string W;
    cin >> W;
    for(int i = 1; i <= W.size(); i++)
        if(W[i-1] == 'C') s[i] = s[i-1]+1;
    else s[i] =  s[i-1] - 1;

    build(rt,1,n);
    int q;
    cin >> q;
    while(q--){
        int l, r;
        scanf("%d%d",&l,&r);
        vale ANS = cnt(rt, 1, n, l, r);
        printf("%d\n", ANS. ans - ANS.S);
        /*int S = 0;
        int M = 0;
        for(int i = l - 1; i <= r; i++){
            if(s[i] + S < s[l - 1]){
                S++;
                M = max(0, M-1);
            }
            if(s[i] > s[r]){
                M = max(M, s[i] - s[r]);
            }

        }
        cout << S + M << endl;*/

    }

}

Compilation message (stderr)

election.cpp:51:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
election.cpp: In function 'int main()':
election.cpp:57:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 1; i <= W.size(); i++)
                    ~~^~~~~~~~~~~
election.cpp:66:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&l,&r);
         ~~~~~^~~~~~~~~~~~~~

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