Submission #681796

#	Time	Username	Problem	Language	Result	Execution time	Memory
681796		Ronin13	Election (BOI18_election)	C++14	100 / 100	1094 ms	70032 KiB

election

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<ll,ll>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax = 5e5 + 1;

struct node{
    ll s, pref;
    node(ll x) : s(x){
        pref = max((ll)0, x);
    }
    node(){
        s = pref = 0;
    }
}t[4 * nmax];

node merg(node a, node b){
    node c;
    c.s = a.s + b.s;
    c.pref = max(a.pref, a.s + b.pref);
    return c;
}

void update(int v, int l, int r, int pos, int val){
    if(l > pos || r < pos) return;
    if(l == r){
        t[v] = {val};
        return;
    }
    int m = (l + r) / 2;
    update(2 * v, l, m, pos, val);
    update(2 * v + 1, m + 1, r, pos, val);
    t[v] = merg(t[2 * v], t[2 * v + 1]);
}

node get(int v, int l, int r, int st, int fin){
    if(l > fin || r < st) return {0};
    if(l >= st && r <= fin)
        return t[v];
    int m=  (l + r) / 2;
    node x = get(2 * v, l, m, st, fin);
    node y = get(2 * v + 1, m + 1, r, st, fin);
    return merg(x, y);
}

int main(){
    int n; cin >> n;
    char c[n + 1];
    for(int i = 1; i <= n; i++)
        cin >> c[i];
    for(int i = 1; i <= n; i++){
        if(c[i] == 'C') update(1, 1, n, i, -1);
        else
            update(1, 1, n, i, 1);
    }
    int q; cin >> q;
    vector <int> ans(q);
    vector <pii> qv[n + 1];
    for(int i = 0; i <q; i++){
        int l, r; cin >> l >> r;
        qv[r].pb({l, i});
    }
    vector <int> cur;
    for(int i = 1; i <= n; i++){
        if(c[i] == 'C'){
            if(!cur.empty()){
                int pos = cur.back();
                update(1, 1, n, pos, 1);
                cur.pop_back();
            }
        }
        else{
            cur.pb(i), update(1, 1, n, i, 0);
        }
        for(auto to : qv[i]){
            int l = to.f;
            int x = cur.end() - lower_bound(cur.begin(), cur.end(), l);
            x += get(1, 1, n, l, i).pref;
            ans[to.s] = x;
        }
    }
    for(int i = 0; i < q; i++)
        cout << ans[i] << "\n";
    return 0;
}

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