Submission #441039

#	Time	Username	Problem	Language	Result	Execution time	Memory
441039		SirCovidThe19th	Election (BOI18_election)	C++14	82 / 100	199 ms	2768 KiB

election

#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; 
    for (int i = 0; i < n; i++){ char c; cin >> c; upd(i, c == '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 / 28
• Subtask 2: 54 / 54
• Subtask 3: 0 / 18