Algoogle

Algorithm for Programming Contest

Codeforces 374D Inna and Sequence

Category: Codeforces Tag: binary-indexed-tree, binary-search, data-structure

Inna and Sequence

問題概要


空の列wとm個の値が昇順に並んだ列aがある. 入力が0か1だったらwの後ろにそれをつなげる.
入力が-1だったら列wのa[i]番目の値をそれぞれ消し, その後詰める.
操作後のwを出力しろ

解法


まず入力をwに加えるものとwからいくつ消すかに分ける.
wに加えるものを一度すべて並べたと考える.
i番目を使うなら1, そうでないなら0とすればそこまでの和で壊されてないもののうち何番目かがわかる.
これはBITで効率的に実装できる.
壊れてないもののうちi番目の値を破壊するときは大きい方から順に和が初めてiになる場所を二分探索して探せば良い.
その場所に0にすれば(-1加えれば)そこが破壊されたことになり, 以降の和も変化して順番が更新される.
全ての破壊が終わったら1になっている場所の値を順に出力すればよい

コード


(374D.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <bits/stdc++.h>
using namespace std;
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i,a) repi(i,0,a)
#define all(u) begin(u),end(u)
#define pb push_back
#define mp make_pair
const int inf = 1e9;
const int M = 1000010;

const int MAX = M;
// BIT is 0 indexed
struct BIT{
    int bit[MAX+1], N;
    BIT(){}
    BIT(int N):N(N){
        memset(bit, 0, sizeof(bit));
    }
    // sum [0,i]
    int sum(int i){
        i++;
        int ret = 0;
        while(i){
            ret += bit[i];
            i -= i&-i;
        }
        return ret;
    }
    // sum [i,j)
    int sum(int i, int j){
        return sum(j-1) - sum(i-1);
    }

    void add(int i, int x){
        i++;
        while(i <= N){
            bit[i] += x;
            i += i&-i;
        }
    }
    int find(int i){
        int lb = -1, ub = N, mid;
        while(ub - lb > 1){
            mid = (lb+ub)/2;
            if(sum(mid) >= i) ub = mid;
            else lb = mid;
        }
        return ub;
    }
};


int n, m, a[M], seq[M], k[M];
int len, ns, ms;
BIT b;

void solve(){
    if(!len){
        puts("Poor stack!");
        return;
    }
    b = BIT(ns);
    rep(i,ns) b.add(i,1);
    rep(i,ms){
        for(int j = k[i]-1; j >= 0; --j){
            int pos = b.find(a[j]);
            b.add(pos,-1);
        }
    }
    rep(i,ns) if(b.sum(i,i+1)) printf("%d", seq[i]);
    puts("");
}

void input(){
    scanf("%d%d", &n, &m);
    rep(i,m) scanf("%d", a+i);
    rep(i,n){
        scanf("%d", seq+ns);
        if(seq[ns] < 0){
            if(a[0] > len) continue;
            k[ms] = lower_bound(a,a+m,len+1)-a;
            len -= k[ms++];
        }
        else ++len, ++ns;
    }
}

int main(){
    input();
    solve();
    return 0;
}

Comments