fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int int64_t
  5. #define endl '\n'
  6. #define vi vector<int>
  7. #define vvi vector<vi>
  8. #define F0(n, i) for(int i = 0; i < n; i++)
  9. #define each(a) for(auto& e: a) 
  10. #define pb push_back
  11.  
  12. template<typename T>
  13. class segtree {
  14. public:
  15. 	vector<T> t;
  16. 	int n;
  17. 	T def;
  18. 	function<T(T, T)> fx;
  19. 	void build(int _n, T _def, function<T(T, T)> _fx) {
  20. 		n = _n; def = _def; fx = _fx;
  21. 		t.assign(n * 2, def);
  22. 		for(int i = n - 1; i; i--) t[i] = fx(t[i * 2], t[i * 2 + 1]);
  23. 	}
  24. 	void build(string& a, T _def, function<T(T, T)> _fx) {
  25. 		n = a.size(); def = _def; fx = _fx;
  26. 		t.assign(n * 2, def);
  27. 		F0(n, i) t[i + n] = {a[i], i};
  28. 		for(int i = n - 1; i; i--) t[i] = fx(t[i * 2], t[i * 2 + 1]);
  29. 	}
  30. 	void update(int i, T v) {
  31. 		for(t[i += n] = v; i > 1; ) {
  32. 			i /= 2;
  33. 			t[i] = fx(t[i * 2], t[i * 2 + 1]);
  34. 		}
  35. 	}
  36. 	T query(int l, int r) {
  37. 		T lans = def, rans = def;
  38. 		for(l += n, r += n; l < r; l /= 2, r /= 2) {
  39. 			if(l % 2) lans = fx(lans, t[l++]);
  40. 			if(r % 2) rans = fx(t[--r], rans);
  41. 		}
  42. 		return fx(lans, rans);
  43. 	}
  44. };
  45.  
  46. void solve() {
  47. 	string s;
  48. 	int k;
  49. 	cin >> s >> k;
  50. 	int n = s.size();
  51. 	segtree<pair<char, int>> Max;
  52. 	Max.build(s, pair<char, int>{'a', n}, [&](pair<char, int> x, pair<char, int> y) {
  53. 		if(x.first >= y.first) return x;
  54. 		return y;
  55. 	});
  56. 	int i = 0;
  57. 	string ans;
  58. 	while(i + k < n) {
  59. 		pair<char, int> q = Max.query(i, i + k + 1);
  60. 		ans.pb(q.first);
  61. 		k -= q.second - i;
  62. 		i = q.second + 1;
  63. 	}
  64. 	cout << ans;
  65. }
  66.  
  67. int32_t main() {
  68. 	int t = 1;
  69. 	cin >> t;
  70. 	while(t--) {
  71. 		solve();
  72. 		cout << endl;
  73. 		cerr << endl;
  74. 	}
  75. }
Success #stdin #stdout #stderr 0.01s 5544KB
comments (?)
stdin
copy 
5
zyxedcba
1
rim
2
baca
1
ayzybyzcy
3
aybzc
3
stdout
copy 
zyxedcb
r
bca
zyyzcy
zc
stderr
copy
https://ideone.com/XriSwK
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!