Submission #311016

#	Time	Username	Problem	Language	Result	Execution time	Memory
311016		gevacrt	Election (BOI18_election)	C++17	100 / 100	2019 ms	73480 KiB

election

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

#define INF INT_MAX
#define MOD 1000000007
#define all(x) x.begin(), x.end()

struct nda{
    int sum, cost;
};

nda merge(nda a, nda b){
    if(a.sum == -1) return b;
    if(b.sum == -1) return a;

    int k = min(a.cost, b.sum);
    a.cost -= k, b.sum -= k;
    return {a.sum+b.sum, a.cost+b.cost};
}

class SegTree{
    vector<nda> st; int l, r;

    void Update(int node, int l, int r, int L, int R, nda val){
        if(r < L or R < l) return;
        if(L <= l and r <= R){
            st[node] = val;
            return;
        }

        int m = (l+r)>>1;
        Update(node*2, l, m, L, R, val);
        Update(node*2+1, m+1, r, L, R, val);
        st[node] = merge(st[node*2], st[node*2+1]);
        return;
    }

    nda Query(int node, int l, int r, int L, int R){
        if(r < L or R < l) return {-1,0};
        if(L <= l and r <= R) return st[node];
        int m = (l+r)>>1;
        auto v1 = Query(node*2, l, m, L, R);
        auto v2 = Query(node*2+1, m+1, r, L, R);
        return merge(v1, v2);
    }

    public:
        SegTree(int l, int r){
            int sz = (r-l+1); st.resize(4*sz, {0,0});
            this->l = l, this->r = r;
        }

        void Update(int L, int R, nda val){
            Update(1, l, r, L, R, val);
            return;
        }

        int Query(int L, int R){
            return Query(1, l, r, L, R).cost;
        }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n; cin >> n;
    string s; cin >> s;
    int q; cin >> q;

    vector<vvi> qry(n);
    for(int x = 0; x < q; x++){
        int l, r; cin >> l >> r;
        qry[l-1].push_back({r-1, x});
    }

    vi ans(q);
    SegTree ST(0, n-1);
    deque<int> tloc;
    for(int x = n-1; x >= 0; x--){
        if(s[x] == 'C'){
            ST.Update(x,x,{1,0});
            if(!tloc.empty()){
                int prev = tloc.front(); tloc.pop_front();
                ST.Update(prev, prev, {0,1});
            }
        }else tloc.push_front(x);


        for(auto qq : qry[x]){
            ans[qq[1]] = upper_bound(all(tloc), qq[0]) - tloc.begin() + ST.Query(x, qq[0]);
        }
    }

    for(int x= 0; x < q; x++)
        cout << ans[x] << endl;

    return 0;
}

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