Submission #1034427

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034427		BF001	Election (BOI18_election)	C++17	0 / 100	2 ms	604 KiB

election

#include<bits/stdc++.h>
using namespace std;
 
#define N 500005 
 
struct node{
    int op, cl, sum;
    node(){
        op = cl = sum = 0;
    }
    node operator + (node o){
        node rt;
        int e = min(op, o.cl);
        rt.op = op + o.op - e;
        rt.cl = cl + o.cl - e;
        rt.sum = sum + o.sum + e;
        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].op = 1, bit[id].cl = 0, bit[id].sum = 0;
            else bit[id].sum = 0, bit[id].op = 0, bit[id].cl = 1;
            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, int typ){
        if (typ == 1) return get(1, 1, n, l, r).op;
        else return get(1, 1, n, l, r).cl;
    }

};


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

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

    int q;
    cin >> q;

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

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