fork(16) download
copy 
  1. #include <algorithm>
  2. #include <iostream>
  3. using namespace std;
  4. const int MAX = 1000005;
  5. pair<int, int> p[MAX];
  6. int par[MAX], size[MAX], ans[MAX];
  7. bool mark[MAX];
  8. int find(int v)
  9. {
  10. 	return (par[v] == v ? v : par[v] = find(par[v]));
  11. }
  12. void merge(int u, int v)
  13. {
  14. 	u = find(u);
  15. 	v = find(v);
  16. 	par[u] = v;
  17. 	size[v] += size[u];
  18. }
  19. int main()
  20. {
  21. 	ios::sync_with_stdio(false);
  22. 	for (int i = 0; i < MAX; i++)
  23. 	{
  24. 		par[i] = i;
  25. 		size[i] = 1;
  26. 	}
  27. 	int n;
  28. 	cin >> n;
  29. 	for (int i = 0; i < n; i++)
  30. 	{
  31. 		cin >> p[i].first;
  32. 		p[i].second = i;
  33. 	}
  34. 	sort(p, p + n, greater<pair<int, int> >());
  35. 	int cur = 1;
  36. 	for (int i = 0; i < n; i++)
  37. 	{
  38. 		int pos = p[i].second;
  39. 		int val = p[i].first;
  40. 		mark[pos] = true;
  41. 		if (pos && mark[pos - 1])
  42. 			merge(pos, pos - 1);
  43. 		if (pos < n - 1 && mark[pos + 1])
  44. 			merge(pos, pos + 1);
  45. 		int sz = size[find(pos)];
  46. 		while (cur <= sz)
  47. 			ans[cur++] = val;
  48. 	}
  49. 	for (int i = 1; i <= n; i++)
  50. 		cout << ans[i] << " ";
  51. 	cout << endl;
  52. 	return 0;
  53. }
  54.  
Runtime error #stdin #stdout 0.03s 23792KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/gQ3ijn
language:
C++14 (gcc 8.3)
created:
9 years 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!