Submission #319362

#	Time	Username	Problem	Language	Result	Execution time	Memory
319362		rqi	Election (BOI18_election)	C++14	100 / 100	1638 ms	61460 KiB

election

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

typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;

#define mp make_pair
#define f first
#define s second
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define pb push_back
#define bk back()

const int MOD = 1000000007;

struct SegTree{
    const static int SZ = 524288;
    int mn[2*SZ];
    int lazy[2*SZ];
    void init(){
        for(int i = 1; i < 2*SZ; i++){
            mn[i] = 0;
            lazy[i] = 0;
        }
    }
    void pull(int ind){
        mn[ind] = min(mn[2*ind], mn[2*ind+1]);
    }
    void push(int ind){
        mn[ind]+=lazy[ind];
        if(ind < SZ){
            lazy[2*ind]+=lazy[ind];
            lazy[2*ind+1]+=lazy[ind];
        }
        lazy[ind] = 0;
    }
    void upd(int lo, int hi, int val, int ind = 1, int L = 0, int R = SZ-1){
        push(ind);
        if(R < lo || L > hi) return;
        
        if(lo <= L && R <= hi){
            lazy[ind]+=val;
            push(ind);
            //cout << ind << " " << L << " " << R << " " << mn[ind] << "\n";
            return;
        }

        int M = (L+R)/2;

        upd(lo, hi, val, 2*ind, L, M);
        upd(lo, hi, val, 2*ind+1, M+1, R);

        pull(ind);
    }
    int query(int lo, int hi, int ind = 1, int L = 0, int R = SZ-1){
        push(ind);
        if(R < lo || L > hi) return MOD;
        
        if(lo <= L && R <= hi){
            // cout << "L,R,mn: " << L << " " << R << " " << mn[ind] << " " << lazy[ind] << "\n";
            // if(ind < SZ){
            //  cout << mn[2*ind] << " " << lazy[2*ind] << "\n";
            // }
            return mn[ind];
        }

        int M = (L+R)/2;

        int Q1 = query(lo, hi, 2*ind, L, M);
        int Q2 = query(lo, hi, 2*ind+1, M+1, R);

        return min(Q1, Q2);
    }
};

const int mx = 500005;

int bt[mx]; //keep track of removed stuff
void upd(int ind, int val){
    assert(1 <= ind && ind < mx);
    while(ind < mx){
        bt[ind]+=val;
        ind+=ind&-ind;
    }
}

int sum(int ind){
    assert(0 <= ind && ind < mx);
    if(ind == 0) return 0;
    int res = 0;
    while(ind > 0){
        res+=bt[ind];
        ind-=ind&-ind;
    }
    return res;
}

int query(int l, int r){
    return sum(r)-sum(l-1);
}

int N;
string votes;
int Q;
int L[mx];
int R[mx];
int ans[mx];
SegTree seg;

int pref[mx];

vi npos[2*mx]; //positions of x+1 --> x, shifted by mx. back is current

void INSERT(int ind){ //removing T at position ind
    //cout << "INSERT " << ind << "\n";
    upd(ind, 1);
    seg.upd(1, ind, 1);
}

int QUERY(int l, int r){
    //cout << "QUERY: " << l << " " << r << "\n";
    int ans = query(l, r);
    //cout << "origans: " << ans << "\n";
    int ival = seg.query(r+1, r+1);
    int mval = seg.query(l, r+1);

    //if(l == 4 && r == 9){
        // for(int i = 1; i <= 12; i++){
        //  cout << seg.query(i, i) << " ";
        // }
        // cout << "\n";
        //cout << ival << " " << mval << "\n";
    //}

    return ans+ival-mval;
}

int main(){
    cin >> N;
    cin >> votes;
    votes = "?" + votes;
    cin >> Q;
    for(int i = 1; i <= Q; i++){
        cin >> L[i] >> R[i];
    }
    seg.init();
    vpi queries;
    for(int i = 1; i <= Q; i++){
        queries.pb(mp(L[i], i));
    }
    sort(all(queries));

    pref[1] = 0;
    for(int i = 2; i <= N+1; i++){
        pref[i] = pref[i-1];
        if(votes[i-1] == 'C'){
            pref[i]++;
        }
        else{
            pref[i]--;
        }
    }

    for(int i = N; i >= 1; i--){
        if(votes[i] == 'T'){
            //cout << "i, pref[i+1] " << i << " " << pref[i+1] << "\n";
            npos[pref[i+1]+mx].pb(i);
        }
    }

    for(int i = -1; i >= -N; i--){
        if(sz(npos[i+mx])){
            //cout << i << " " << npos[i+mx].bk << "\n";
            INSERT(npos[i+mx].bk);
        }
    }

    int cursum = 0;
    for(int i = N+1; i >= 1; i--){
        if(i != N+1){
            if(votes[i] == 'C'){
                cursum++;
            }
            else if(votes[i] == 'T'){
                cursum--;
            }
        }
        seg.upd(i, i, cursum);
    }



    int curL = 1;
    
    for(int q = 0; q < Q; q++){
        int qind = queries[q].s;

        //cout << "qind: " << qind << "\n";

        while(curL < L[qind]){
            if(votes[curL] == 'C'){
                if(sz(npos[pref[curL+1]-1+mx])){
                    INSERT(npos[pref[curL+1]-1+mx].bk);
                }
            }
            else if(votes[curL] == 'T'){
                npos[pref[curL+1]+mx].pop_back();
                //ERASE(npos[pref[curL]+mx].bk); doesn't seem necessary?
            }
            curL++;
        }

        ans[qind] = QUERY(L[qind], R[qind]);
    }

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

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