oj.uz

Submission #440996

# Submission time Handle Problem Language Result Execution time Memory
440996 2021-07-03T21:26:11 Z SirCovidThe19th Election (BOI18_election) C++14
0 / 100
 20 ms 332 KB 
#include <bits/stdc++.h>
using namespace std;

struct node{ int rAns, rRem, lAns, lRem; };

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

node comb(node a, node b){
    return{
        a.rAns+max(b.rAns-a.rRem, 0), b.rRem+max(a.rRem-b.rAns, 0),
        b.lAns+max(a.lAns-b.lRem, 0), b.rRem+max(b.lRem-a.lAns, 0)
    };
}
void upd(int i, int val){
    seg[i += n] = {val, 1-val, val, 1-val};
    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 = {}, ret;
    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);
    }ret = comb(retL, retR); return max(ret.lAns, ret.rAns); 
}

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

Subtask #1
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -