Submission #64197

#	Time	Username	Problem	Language	Result	Execution time	Memory
64197		someone_aa	Election (BOI18_election)	C++17	100 / 100	1593 ms	47128 KiB

election

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 500100;
vector<pair<int,int>>events[maxn];
int arr[maxn], answer[maxn], n, q;

struct node {
public:
    int l, r;
    int sum, minsuf;
} tree[4*maxn];

node mergef(node a, node b) {
    node c;
    c.l = a.l; c.r = b.r;
    c.sum = a.sum + b.sum;
    c.minsuf = min(b.minsuf, a.minsuf + b.sum);
    return c;
}

void build(int li=1, int ri=n, int index=1) {
    if(li == ri) {
        tree[index].l = li; tree[index].r = ri;
        tree[index].sum = arr[li];
        tree[index].minsuf = min(0, arr[li]);
    }
    else {
        int mid = (li+ri)/2;
        build(li, mid, 2*index);
        build(mid+1,ri,2*index+1);
        tree[index] = mergef(tree[2*index], tree[2*index+1]);
    }
    /*cout<<index<<": ["<<li<<", "<<ri<<"]\n";
    cout<<tree[index].sum<<" "<<tree[index].minsuf<<"\n";*/
}

node query(int ql, int qr, int index=1) {
    if(qr < tree[index].l || tree[index].r < ql) return {0,0,0,4*maxn};
    else if(tree[index].l >= ql && tree[index].r <= qr) return tree[index];
    else {
        return mergef(query(ql,qr,2*index), query(ql,qr,2*index+1));
    }
}

void update(int ul, int val, int index=1) {
    if(tree[index].l == tree[index].r) {
        arr[ul] = val;
        tree[index].sum = val;
        tree[index].minsuf = min(val, 0);
    }
    else {
        int mid = (tree[index].l+tree[index].r)/2;
        if(ul <= mid) update(ul,val,2*index);
        else update(ul,val,2*index+1);
        tree[index] = mergef(tree[2*index], tree[2*index+1]);
    }
}

int main() {
    cin>>n;
    char c;
    for(int i=1;i<=n;i++) {
        cin>>c;
        if(c == 'C') arr[i] = 1;
        else arr[i] = -1;
    }
    build();

    cin>>q;
    int l, r;
    for(int i=1;i<=q;i++) {
        cin>>l>>r;
        events[l].pb(mp(r,i));
    }


    vector<int>st;
    for(int i=n;i>=1;i--) {
        if(arr[i] == -1) {
            update(i, 0);
            st.pb(i);
        }
        else if(arr[i] == 1 && st.size()>0) {
            update(st.back(), -1);
            st.pop_back();
        }

        /*cout<<i<<": \n";
        for(int i:st) cout<<i<<" ";
        cout<<"\n Suffix: "<<query(i, n).minsuf<<"\n";*/

        for(auto j:events[i]) {
            l = i, r = j.first;
            answer[j.second] = upper_bound(st.rbegin(), st.rend(), r) - st.rbegin() - query(l, r).minsuf;
        }
    }

    for(int i=1;i<=q;i++) {
        cout<<answer[i]<<"\n";
    }

    return 0;
}

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