Advertisement
Guest User

Untitled

a guest
Jul 16th, 2019
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.18 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define F first
  4. #define S second
  5. #define PB push_back
  6. #define MP make_pair
  7. #define REP(i,a,b) for (int i = a; i <= b; i++)
  8. #define debug(i) cout << i << endl;
  9. #define debugarr(a) for(auto i : a) cout << i << " ";
  10.  
  11. #define ll long long
  12. #define vi vector<int>
  13. #define vll vector<ll>
  14. #define pi pair<int,int>
  15. #define pll pair<ll, ll>
  16. #define vpi vector<pi>
  17.  
  18. #define N 100010
  19. #define LEFT(x) (x<<1)
  20. #define RIGHT(x) ((x<<1)|1)
  21.  
  22. using namespace std;
  23.  
  24. int arr[N];
  25. pi tree[N * 4];
  26.  
  27. pi query(int i, int l, int r, int x, int y) {
  28. if(l >= x && r <= y) return tree[i];
  29. else if(r < x || l > y) return MP(-1,-1);
  30. else {
  31. int mid = (l+r)>>1;
  32. pi res = MP(-1, -1);
  33. if(x <= mid)
  34. res = query(LEFT(i), l, mid, x, y);
  35. if(y > mid) {
  36. pi q = query(RIGHT(i), mid+1, r, x, y);
  37. if(q.F > res.F)
  38. res = q;
  39. else if(q.F == res.F && q.S < res.S)
  40. res = q;
  41. }
  42. return res;
  43. }
  44. }
  45.  
  46. void build(int i, int l, int r) {
  47. if(l == r) tree[i] = MP(arr[l], l);
  48. else {
  49. int mid = (l+r)>>1;
  50. build(LEFT(i), l, mid);
  51. build(RIGHT(i), mid+1, r);
  52.  
  53. if(tree[LEFT(i)].F > tree[RIGHT(i)].F)
  54. tree[i] = tree[LEFT(i)];
  55. else if(tree[LEFT(i)].F < tree[RIGHT(i)].F)
  56. tree[i] = tree[RIGHT(i)];
  57. else {
  58. if(tree[LEFT(i)].S < tree[RIGHT(i)].S)
  59. tree[i] = tree[LEFT(i)];
  60. else
  61. tree[i] = tree[RIGHT(i)];
  62. }
  63. }
  64. }
  65.  
  66. int main() {
  67. ios_base::sync_with_stdio(false);
  68.  
  69. int n, d;
  70. while(cin >> n >> d && n != 0) {
  71. memset(tree, 0, sizeof tree);
  72. int need = n - d;
  73. for(int i = 1; i <= n; i++) {
  74. char k;
  75. cin >> k;
  76. arr[i] = k - '0';
  77. }
  78. build(1, 1, n);
  79.  
  80. int last_choose = -1;
  81. string ans = "";
  82. while(need--) {
  83. pi next = query(1, 1, n, last_choose+1, n - need);
  84. last_choose = next.S;
  85. ans += (char) next.F + '0';
  86. }
  87. cout << ans << endl;
  88. }
  89. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement