Submission #69538

#	Time	Username	Problem	Language	Result	Execution time	Memory
69538		3zp	Election (BOI18_election)	C++14	0 / 100	3 ms	760 KiB

election

#include<bits/stdc++.h>
using namespace std;
struct NODE{
    int S, mir, mal, ans;
    NODE *L, *R;
    void CO(NODE *&X, NODE *&Y){
        if(!X && !Y) return;
        if(!X) {
            this -> S = Y -> S;
            this -> mir = Y -> mir;
            this -> mal = Y -> mal;
            this -> ans = Y -> ans;
            return;
        }
        if(!Y){
            this -> S = X -> S;
            this -> mir = X -> mir;
            this -> mal = X -> mal;
            this -> ans = X -> ans;
            return;
        }
        this->S = X->S+ Y->S;
        this->mir = min(Y->mir + X->S, X->mir);
        this->mal = max(X->mal, Y->mal + X->S);
        this->ans = max(X->ans, Y->ans);
        this->ans = max(this->ans, Y->mal + X->S - X->mir);

    }
    void upd(){
        this->CO(this->L, this->R);
    }
};
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->S = k;
        x->mir = min(0, k);
        x->mal = max(0, k);
        x->ans = max(k, 0);
    }
    else{
        int mid = (l + r)/2;
        build(x->L, l, mid);
        build(x->R, mid+1, r);
        x->upd();
    }
 }
void cnt(NODE *&x, NODE *&ans, int l, int r, int a, int b){
    if(a > r || b < l) return;
    if(l >= a && r <= b) {ans = x; return;}
    int mid = (l + r)/2;
    NODE *ans1 = NULL, *ans2 = NULL;
    cnt(x->L, ans1, l, mid, a ,b);
    cnt(x->R, ans2, mid+1, r, a, b);
    ans = new NODE();
    ans->CO(ans1, ans2);
    if(ans1)delete ans1;
    if(ans2)delete ans2;
}
NODE *rt, *ANS;
main(){
    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);
        cnt(rt, ANS, 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:63:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
election.cpp: In function 'int main()':
election.cpp:68:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 1; i <= W.size(); i++)
                    ~~^~~~~~~~~~~
election.cpp:77: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: 0 / 28
• Subtask 2: 0 / 54
• Subtask 3: 0 / 18