oj.uz

Submission #69535

# Submission time Handle Problem Language Result Execution time Memory
69535 2018-08-21T08:14:20 Z 3zp Election (BOI18_election) C++14
82 / 100
 1642 ms 263168 KB 
#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);
}
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

election.cpp:61:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
election.cpp: In function 'int main()':
election.cpp:66:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 1; i <= W.size(); i++)
                    ~~^~~~~~~~~~~
election.cpp:75: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.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2168 KB Output is correct
2 Correct 6 ms 2168 KB Output is correct
3 Correct 5 ms 2240 KB Output is correct
4 Correct 6 ms 2256 KB Output is correct
5 Correct 7 ms 2304 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2168 KB Output is correct
2 Correct 6 ms 2168 KB Output is correct
3 Correct 5 ms 2240 KB Output is correct
4 Correct 6 ms 2256 KB Output is correct
5 Correct 7 ms 2304 KB Output is correct
6 Correct 248 ms 98588 KB Output is correct
7 Correct 227 ms 104264 KB Output is correct
8 Correct 266 ms 104264 KB Output is correct
9 Correct 208 ms 104264 KB Output is correct
10 Correct 332 ms 104264 KB Output is correct
11 Correct 303 ms 104264 KB Output is correct
12 Correct 298 ms 104264 KB Output is correct
13 Correct 282 ms 104656 KB Output is correct
14 Correct 246 ms 105580 KB Output is correct
15 Correct 266 ms 106600 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2168 KB Output is correct
2 Correct 6 ms 2168 KB Output is correct
3 Correct 5 ms 2240 KB Output is correct
4 Correct 6 ms 2256 KB Output is correct
5 Correct 7 ms 2304 KB Output is correct
6 Correct 248 ms 98588 KB Output is correct
7 Correct 227 ms 104264 KB Output is correct
8 Correct 266 ms 104264 KB Output is correct
9 Correct 208 ms 104264 KB Output is correct
10 Correct 332 ms 104264 KB Output is correct
11 Correct 303 ms 104264 KB Output is correct
12 Correct 298 ms 104264 KB Output is correct
13 Correct 282 ms 104656 KB Output is correct
14 Correct 246 ms 105580 KB Output is correct
15 Correct 266 ms 106600 KB Output is correct
16 Runtime error 1642 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Halted 0 ms 0 KB -