fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define all(x) (x).begin(), (x).end()
  4. #define allr(x) (x).rbegin(), (x).rend()
  5. #define gsize(x) (int)((x).size())
  6.  
  7. const char nl = '\n';
  8. typedef long long ll;
  9. typedef long double ld;
  10.  
  11. using namespace std;
  12.  
  13. int main() {
  14. 	ios::sync_with_stdio(0); cin.tie(0);
  15.  
  16. 	int T;
  17. 	cin >> T;
  18. 	while (T--) {
  19. 		int n;
  20. 		cin >> n;
  21.  
  22. 		vector<int> a(n);
  23. 		map<int, vector<int>> p;
  24. 		for (int i = 0; i < n; i++) {
  25. 			cin >> a[i];
  26. 			p[a[i]].push_back(i);
  27. 		}
  28.  
  29. 		int ans = 0;
  30. 		set<int> ts;
  31. 		for (int i = 0; i < n - 1; i++) {
  32. 			if (a[i] > a[i + 1]) ts.insert(i);
  33. 		}
  34.  
  35. 		while (!ts.empty()) {
  36. 			int i = *ts.begin();
  37. 			int x;
  38. 			if (a[i] > 0) {
  39. 				x = a[i];
  40. 			} else {
  41. 				x = a[i + 1];
  42. 			}
  43.  
  44. 			for (int j: p[x]) {
  45. 				a[j] = 0;
  46. 				ts.erase(j - 1);
  47. 				ts.erase(j);
  48. 				if (j > 0 && a[j - 1] > a[j]) ts.insert(j - 1);
  49. 				if (j + 1 < n && a[j] > a[j + 1]) ts.insert(j);
  50. 			}
  51. 			ans++;
  52. 		}
  53.  
  54. 		cout << ans << nl;
  55. 	}
  56. }
Success #stdin #stdout 0s 5292KB
comments (?)
stdin
copy 
5
3
3 3 2
4
1 3 1 3
5
4 1 5 3 2
4
2 4 1 2
1
1
stdout
copy 
1
2
4
3
0
https://ideone.com/114daw
language:
C++ (gcc 8.3)
created:
39 days 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!