Guest User

Untitled

a guest
Jun 25th, 2018
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.63 KB | None | 0 0
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. #include <math.h>
  5. #include <string>
  6. #include <sstream>
  7. #include <iomanip>
  8. #include <stdio.h>
  9. #include <stdlib.h>
  10. #include <ctime>
  11. #include <time.h>
  12. #include <string.h>
  13. #include <algorithm>
  14. #include <queue>
  15. #include <stack>
  16. #include <vector>
  17. #include <map>
  18. #include <set>
  19. using namespace std;
  20.  
  21. const int off = 1<<19;
  22.  
  23. int T[ off*2 ][2];
  24. int n, k;
  25. char in[off];
  26.  
  27. void fill(){
  28.     scanf("%s", in);
  29.     for( int x = 0; x < n; x++ ){
  30.         T[ off+x ][0] = in[x];
  31.         T[ off+x ][1] = x;
  32.     }
  33.     for( int x = off -1; x > 0; x-- )
  34.         if( T[ x*2 ][0] < T[ x*2+1 ][0] ){
  35.             T[ x ][0] = T[ x*2+1 ][0];
  36.             T[ x ][1] = T[ x*2+1 ][1];
  37.         }else{
  38.             T[ x ][0] = T[ x*2 ][0];
  39.             T[ x ][1] = T[ x*2 ][1];
  40.         }
  41. }
  42. pair<int,int> query( int a, int b, int lo = 0, int hi = off, int p = 1 ){
  43.     if( a >= hi || b <= lo )
  44.         return make_pair(-1,-1);
  45.     if( lo >= a && hi <= b ){
  46.         return make_pair(T[p][0],T[p][1]);
  47.     }
  48.     pair<int,int> aa=query( a,b,lo,(lo+hi)/2,p*2),bb=query( a,b,(lo+hi)/2,hi,p*2+1);
  49.     if( aa.first > bb.first )
  50.         return aa;
  51.     else if( aa.first<bb.first )
  52.         return bb;
  53.     else if( aa.second > bb.second )
  54.         return aa;
  55.     else
  56.         return bb;
  57. }
  58. int main(){
  59.     scanf("%d %d", &n, &k);
  60.     fill();
  61.     pair<int ,int > t;
  62.     for( int x = 0; x < n; x++ ){
  63.         t = query( x, x+k+1 );
  64.         if( k - t.second+x >= 0 ){
  65.             k-= t.second-x;
  66.             x = t.second;
  67.         }
  68.         printf("%c",in[ x ]);
  69.     }
  70.     putchar('\n');
  71. }
Add Comment
Please, Sign In to add comment