oj.uz

Submission #441040

# Submission time Handle Problem Language Result Execution time Memory
441040 2021-07-04T00:59:37 Z SirCovidThe19th Election (BOI18_election) C++14
100 / 100
 1639 ms 27184 KB 
#include <bits/stdc++.h>
using namespace std;

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

int n; node seg[1000005]; // -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 5 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 5 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 202 ms 2924 KB Output is correct
7 Correct 185 ms 2928 KB Output is correct
8 Correct 187 ms 2804 KB Output is correct
9 Correct 196 ms 2756 KB Output is correct
10 Correct 195 ms 2788 KB Output is correct
11 Correct 191 ms 2884 KB Output is correct
12 Correct 190 ms 3008 KB Output is correct
13 Correct 190 ms 3012 KB Output is correct
14 Correct 191 ms 2936 KB Output is correct
15 Correct 191 ms 2800 KB Output is correct

Subtask #3
18.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 5 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 202 ms 2924 KB Output is correct
7 Correct 185 ms 2928 KB Output is correct
8 Correct 187 ms 2804 KB Output is correct
9 Correct 196 ms 2756 KB Output is correct
10 Correct 195 ms 2788 KB Output is correct
11 Correct 191 ms 2884 KB Output is correct
12 Correct 190 ms 3008 KB Output is correct
13 Correct 190 ms 3012 KB Output is correct
14 Correct 191 ms 2936 KB Output is correct
15 Correct 191 ms 2800 KB Output is correct
16 Correct 1525 ms 18508 KB Output is correct
17 Correct 1473 ms 25780 KB Output is correct
18 Correct 1501 ms 26060 KB Output is correct
19 Correct 1381 ms 25632 KB Output is correct
20 Correct 1491 ms 25216 KB Output is correct
21 Correct 1542 ms 27004 KB Output is correct
22 Correct 1514 ms 27012 KB Output is correct
23 Correct 1501 ms 27184 KB Output is correct
24 Correct 1570 ms 26856 KB Output is correct
25 Correct 1639 ms 26300 KB Output is correct