Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define F first
- #define S second
- #define PB push_back
- #define MP make_pair
- #define REP(i,a,b) for (int i = a; i <= b; i++)
- #define debug(i) cout << i << endl;
- #define debugarr(a) for(auto i : a) cout << i << " ";
- #define ll long long
- #define vi vector<int>
- #define vll vector<ll>
- #define pi pair<int,int>
- #define pll pair<ll, ll>
- #define vpi vector<pi>
- #define N 100010
- #define LEFT(x) (x<<1)
- #define RIGHT(x) ((x<<1)|1)
- using namespace std;
- int arr[N];
- pi tree[N * 4];
- pi query(int i, int l, int r, int x, int y) {
- if(l >= x && r <= y) return tree[i];
- else if(r < x || l > y) return MP(-1,-1);
- else {
- int mid = (l+r)>>1;
- pi res = MP(-1, -1);
- if(x <= mid)
- res = query(LEFT(i), l, mid, x, y);
- if(y > mid) {
- pi q = query(RIGHT(i), mid+1, r, x, y);
- if(q.F > res.F)
- res = q;
- else if(q.F == res.F && q.S < res.S)
- res = q;
- }
- return res;
- }
- }
- void build(int i, int l, int r) {
- if(l == r) tree[i] = MP(arr[l], l);
- else {
- int mid = (l+r)>>1;
- build(LEFT(i), l, mid);
- build(RIGHT(i), mid+1, r);
- if(tree[LEFT(i)].F > tree[RIGHT(i)].F)
- tree[i] = tree[LEFT(i)];
- else if(tree[LEFT(i)].F < tree[RIGHT(i)].F)
- tree[i] = tree[RIGHT(i)];
- else {
- if(tree[LEFT(i)].S < tree[RIGHT(i)].S)
- tree[i] = tree[LEFT(i)];
- else
- tree[i] = tree[RIGHT(i)];
- }
- }
- }
- int main() {
- ios_base::sync_with_stdio(false);
- int n, d;
- while(cin >> n >> d && n != 0) {
- memset(tree, 0, sizeof tree);
- int need = n - d;
- for(int i = 1; i <= n; i++) {
- char k;
- cin >> k;
- arr[i] = k - '0';
- }
- build(1, 1, n);
- int last_choose = -1;
- string ans = "";
- while(need--) {
- pi next = query(1, 1, n, last_choose+1, n - need);
- last_choose = next.S;
- ans += (char) next.F + '0';
- }
- cout << ans << endl;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement