fork download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <algorithm>	
  4.  
  5. using namespace std;
  6.  
  7. string s;
  8. int k, n, vt = 1;
  9. pair<int, int> a[1000001], tree[4000001];
  10.  
  11. void setup(int id, int l, int r)
  12. {
  13. 	if (l == r)
  14. 	{
  15. 		tree[id] = a[l];
  16. 		return;
  17. 	}
  18.  
  19. 	int mid = (l + r) / 2;
  20. 	setup(id * 2, l, mid);
  21. 	setup(id * 2 + 1, mid + 1, r);
  22. 	if (tree[id * 2].first >= tree[id * 2 + 1].first)
  23. 		tree[id] = tree[id * 2];
  24. 	else
  25. 		tree[id] = tree[id * 2 + 1];
  26. }
  27.  
  28. pair<int, int> get_val(int id, int l, int r, int u, int v)
  29. {
  30. 	if (l > v || r < u)
  31. 		return make_pair(-1, -1);
  32. 	if (l >= u && r <= v)
  33. 		return tree[id];
  34.  
  35. 	int mid = (l + r) / 2;
  36. 	pair<int, int> left = get_val(id * 2, l, mid, u, v);
  37. 	pair<int, int> right = get_val(id * 2 + 1, mid + 1, r, u, v);
  38. 	if (left.first >= right.first)
  39. 		return left;
  40. 	else
  41. 		return right;
  42. }
  43.  
  44.  
  45. void inp()
  46. {
  47. 	getline(cin, s);
  48. 	cin >> k;
  49. 	n = s.size();
  50. 	k = n - k;
  51. 	s = 'x' + s;
  52. 	for (int i = 1; i <= s.size() - 1; i++)
  53. 		a[i] = make_pair(s[i] - '0', i);
  54. 	setup(1, 1, n);
  55. }
  56. void xuli()
  57. {
  58. 	while (k > 0)
  59. 	{
  60. 		pair<int, int> ans = get_val(1, 1, n, vt, n - k + 1);
  61. 		cout << ans.first;
  62. 		vt = ans.second + 1;
  63. 		k--;
  64. 	}
  65. }
  66. int main()
  67. {
  68. 	inp();
  69. 	xuli();
  70. }
  71.  
Success #stdin #stdout 0.01s 5632KB
comments (?)
stdin
copy 
2357111317192329
6
stdout
copy 
7317192329
https://ideone.com/Elv9qa
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!