Submission #384571

#	Time	Username	Problem	Language	Result	Execution time	Memory
384571		Peti	Election (BOI18_election)	C++14	100 / 100	1698 ms	97360 KiB

election

#include <bits/stdc++.h>

using namespace std;

struct segment_tree{
    vector<int> st, stmin, stadd;
    int maxn = 0;

    void init(int n){
        maxn = n;
        st.assign(4*n, 0);
        stmin.assign(4*n, 0);
        stadd.assign(4*n, 0);
        return;
    }

    void pont_upd(int x, int l, int r){
        if(l+1 == r){
            st[x] = stmin[x] = stadd[x];
            return;
        }
        st[x] = st[2*x+1] + st[2*x+2] + stadd[x] * (r-l);
        stmin[x] = min(stmin[2*x+1], stmin[2*x+2]) + stadd[x];
        return;
    }

    void add(int L, int R, int c, int x, int l, int r){
        if(r <= L || R <= l)
            return;
        if(L <= l && r <= R){
            stadd[x] += c;
            pont_upd(x, l, r);
            return;
        }
        int m = (l+r)/2;
        add(L, R, c, 2*x+1, l, m);
        add(L, R, c, 2*x+2, m, r);
        pont_upd(x, l, r);
        return;
    }

    void add(int l, int r, int c){
        add(l, r, c, 0, 0, maxn);
        return;
    }

    int minert(int L, int R, int x, int l, int r){
        if(r <= L || R <= l)
            return (int)1e9;
        if(L <= l && r <= R)
            return stmin[x];
        int m = (l+r)/2;
        return min(minert(L, R, 2*x+1, l, m), minert(L, R, 2*x+2, m, r)) + stadd[x];
    }

    int minert(int l, int r) {return minert(l, r, 0, 0, maxn); }

    int ossz(int L, int R, int c, int x, int l, int r){
        if(r <= L || R <= l)
            return 0;
        if(L <= l && r <= R)
            return st[x] + c*(r-l);
        int m = (l+r)/2;
        return ossz(L, R, c + stadd[x], 2*x+1, l, m)+ossz(L, R, c + stadd[x], 2*x+2, m, r);
    }

    int ossz(int l, int r) {return ossz(l, r, 0, 0, 0, maxn); }
};

int main()
{
    cin.sync_with_stdio(false);
    cin.tie(0);

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

    vector<int> ki(q);
    vector<vector<pair<int, int>>> v(n);

    for(int i = 0; i < q; i++){
        int l, r;
        cin>>l>>r;
        v[l-1].push_back(make_pair(r-1, i));
    }

    segment_tree st, st2;
    st.init(n+1);
    st2.init(n+1);

    set<int> inds;
    for(int i = 0; i < n; i++){
        if(s[i] == 'T'){
            inds.insert(i);
            st2.add(i, i+1, 1);
        }
    }

    for(int i = n-1; i >= 0; i--){
        if(s[i] == 'C'){
            auto it = inds.lower_bound(i);
            if(it != inds.end()){
                st2.add((*it), (*it)+1, -1);
                st.add(0, (*it)+1, -1);
                inds.erase(it);
            }
            st.add(0, i+1, 1);
        }
        for(pair<int, int> temp : v[i])
            ki[temp.second] = st2.ossz(i, temp.first+1) + st.minert(temp.first+1, temp.first+2) - st.minert(i, temp.first+2);
    }

    for(int x : ki)
        cout<<x<<"\n";

    return 0;
}

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