Submission #1034560

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034560		BF001	Election (BOI18_election)	C++17	100 / 100	376 ms	42992 KiB

election

#include<bits/stdc++.h>
using namespace std;
 
#define N 500005 
 
struct node{
    int rm, lm, sum, ans;
    node(){
        rm = lm = sum = ans = 0;
    }
    node operator + (node o){
        node rt;
        rt.sum = sum + o.sum;
        rt.lm = max(lm, sum + o.lm);
        rt.rm = max(o.rm, o.sum + rm);
        rt.ans = max({lm + o.rm, ans + o.sum, sum + o.ans});
        return rt;
    }
};

struct segtree
{

    int n;
    vector<node> bit;

    segtree(int siz){
        n = siz;
        bit.resize(4 * siz + 1);
    }

    void ud(int id, int l, int r, int pos, int typ){
        if (l > pos || r < pos) return;
        if (l == r){
            if (typ == 1) bit[id].rm = bit[id].lm = bit[id].sum = bit[id].ans = 1;
            else bit[id].rm = 0, bit[id].lm = 0, bit[id].sum = -1, bit[id].ans = 0;
            return;
        }
        int mid = (l + r) >> 1;
        ud(id * 2, l, mid, pos, typ);
        ud(id * 2 + 1, mid + 1, r, pos, typ);
        bit[id] = bit[id * 2] + bit[id * 2 + 1];
    }

    node nll;

    node get(int id, int l, int r, int u, int v){
        if (l > v || r < u) return nll;
        if (l >= u && r <= v) return bit[id];
        int mid = (l + r) >> 1;
        node t = get(id * 2, l, mid, u, v);
        node tt = get(id * 2 + 1, mid + 1, r, u, v);
        return (t + tt);
    }

    void insert(int pos, int typ){
        ud(1, 1, n, pos, typ);
    }

    int get(int l, int r){
        return get(1, 1, n, l, r).ans;
    }

};


signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
 
    int n;
    string s;
    cin >> n;
    cin >> s;
    
    segtree s1(n);

    s = " " + s;
    for (int i = 1; i <= n; i++){
        if (s[i] == 'C'){
            s1.insert(i, -1);
        }
        else s1.insert(i, 1);   
    }
    int q;
    cin >> q;

    while (q--){
        int l, r;
        cin >> l >> r;
        cout << s1.get(l, r) << "\n";
    }
    
    return 0;
}

• Subtask 1: 28 / 28
• Subtask 2: 54 / 54
• Subtask 3: 18 / 18