oj.uz

Submission #441035

# Submission time Handle Problem Language Result Execution time Memory
441035 2021-07-04T00:50:38 Z SirCovidThe19th Election (BOI18_election) C++14
82 / 100
 1321 ms 9720 KB 
#include <bits/stdc++.h>
using namespace std;

struct node{ int pre, suf, sum, ans; };

int n; node seg[500005]; // -1 - C, 1 - T

node comb(node a, node b){
    return{
        max(a.pre, a.sum+b.pre),
        max(b.suf, b.sum+a.suf),
        a.sum+b.sum,
        max(max(a.sum+b.ans, b.sum+a.ans), a.pre+b.suf)
    };
}
void upd(int i, int val){
    seg[i += n] = {max(val, 0), max(val, 0), val, max(val, 0)};
    for (i /= 2; i > 0; i /= 2) seg[i] = comb(seg[i*2], seg[i*2+1]);
}
int query(int l, int r){
    node retL = {}, retR = {};
    for (l += n, r += n; l <= r; l /= 2, r /= 2){
        if (l%2 == 1) retL = comb(retL, seg[l++]);
        if (r%2 == 0) retR = comb(seg[r--], retR);
    }return comb(retL, retR).ans;
}

int main(){ 
    cin >> n; string s; cin >> s;
    for (int i = 0; i < n; i++) upd(i, s[i] == 'C' ? -1 : 1);
    int q; cin >> q;
    while (q--){
        int l, r; cin >> l >> r; 
        cout<<query(l-1, r-1)<<endl;
    }
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 332 KB Output is correct
2 Correct 5 ms 332 KB Output is correct
3 Correct 6 ms 332 KB Output is correct
4 Correct 5 ms 332 KB Output is correct
5 Correct 5 ms 332 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 332 KB Output is correct
2 Correct 5 ms 332 KB Output is correct
3 Correct 6 ms 332 KB Output is correct
4 Correct 5 ms 332 KB Output is correct
5 Correct 5 ms 332 KB Output is correct
6 Correct 187 ms 3840 KB Output is correct
7 Correct 187 ms 3728 KB Output is correct
8 Correct 191 ms 3688 KB Output is correct
9 Correct 197 ms 3816 KB Output is correct
10 Correct 188 ms 3692 KB Output is correct
11 Correct 200 ms 3884 KB Output is correct
12 Correct 194 ms 3936 KB Output is correct
13 Correct 189 ms 3908 KB Output is correct
14 Correct 196 ms 3804 KB Output is correct
15 Correct 200 ms 3876 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 332 KB Output is correct
2 Correct 5 ms 332 KB Output is correct
3 Correct 6 ms 332 KB Output is correct
4 Correct 5 ms 332 KB Output is correct
5 Correct 5 ms 332 KB Output is correct
6 Correct 187 ms 3840 KB Output is correct
7 Correct 187 ms 3728 KB Output is correct
8 Correct 191 ms 3688 KB Output is correct
9 Correct 197 ms 3816 KB Output is correct
10 Correct 188 ms 3692 KB Output is correct
11 Correct 200 ms 3884 KB Output is correct
12 Correct 194 ms 3936 KB Output is correct
13 Correct 189 ms 3908 KB Output is correct
14 Correct 196 ms 3804 KB Output is correct
15 Correct 200 ms 3876 KB Output is correct
16 Incorrect 1321 ms 9720 KB Output isn't correct
17 Halted 0 ms 0 KB -