Submission #440996

#	Time	Username	Problem	Language	Result	Execution time	Memory
440996		SirCovidThe19th	Election (BOI18_election)	C++14	0 / 100	20 ms	332 KiB

election

#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
• Subtask 2: 0 / 54
• Subtask 3: 0 / 18