oj.uz

답안 #319362

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
319362 2020-11-05T02:30:37 Z rqi Election (BOI18_election) C++14
100 / 100
 1638 ms 61460 KB 
#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.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 32108 KB Output is correct
2 Correct 25 ms 32364 KB Output is correct
3 Correct 25 ms 32108 KB Output is correct
4 Correct 25 ms 32268 KB Output is correct
5 Correct 25 ms 32236 KB Output is correct

Subtask #2
54.0 / 54.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 32108 KB Output is correct
2 Correct 25 ms 32364 KB Output is correct
3 Correct 25 ms 32108 KB Output is correct
4 Correct 25 ms 32268 KB Output is correct
5 Correct 25 ms 32236 KB Output is correct
6 Correct 205 ms 35540 KB Output is correct
7 Correct 173 ms 35412 KB Output is correct
8 Correct 202 ms 35408 KB Output is correct
9 Correct 197 ms 35412 KB Output is correct
10 Correct 199 ms 35668 KB Output is correct
11 Correct 213 ms 35924 KB Output is correct
12 Correct 209 ms 35664 KB Output is correct
13 Correct 211 ms 36324 KB Output is correct
14 Correct 199 ms 35664 KB Output is correct
15 Correct 195 ms 35712 KB Output is correct

Subtask #3
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 32108 KB Output is correct
2 Correct 25 ms 32364 KB Output is correct
3 Correct 25 ms 32108 KB Output is correct
4 Correct 25 ms 32268 KB Output is correct
5 Correct 25 ms 32236 KB Output is correct
6 Correct 205 ms 35540 KB Output is correct
7 Correct 173 ms 35412 KB Output is correct
8 Correct 202 ms 35408 KB Output is correct
9 Correct 197 ms 35412 KB Output is correct
10 Correct 199 ms 35668 KB Output is correct
11 Correct 213 ms 35924 KB Output is correct
12 Correct 209 ms 35664 KB Output is correct
13 Correct 211 ms 36324 KB Output is correct
14 Correct 199 ms 35664 KB Output is correct
15 Correct 195 ms 35712 KB Output is correct
16 Correct 1547 ms 57436 KB Output is correct
17 Correct 1213 ms 55328 KB Output is correct
18 Correct 1526 ms 57384 KB Output is correct
19 Correct 1389 ms 56868 KB Output is correct
20 Correct 1513 ms 57504 KB Output is correct
21 Correct 1638 ms 60328 KB Output is correct
22 Correct 1532 ms 58752 KB Output is correct
23 Correct 1602 ms 61460 KB Output is correct
24 Correct 1525 ms 58760 KB Output is correct
25 Correct 1417 ms 57584 KB Output is correct