fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define jjs(i, s, x) for (int i = (s); i < (x); i++)
  4. #define jjl(i, x) jjs(i, 0, x)
  5. #define ji(x) jjl(i, x)
  6. #define rint(x) scanf("%d", &(x))
  7.  
  8. using namespace std;
  9.  
  10. const int MX = 100010;
  11. const int TMX = MX * 4;
  12. int minPrefix[TMX], sum[TMX];
  13. int N;
  14.  
  15. void add(int idx, int a, int b, int pos, int val)
  16. {
  17. 	if (pos < a || pos > b)
  18. 		return;
  19. 	if (a == b)
  20. 	{
  21. 		sum[idx] += val;
  22. 		minPrefix[idx] = min(sum[idx], 0);
  23. 	}
  24. 	else
  25. 	{
  26. 		int l = idx * 2 + 1;
  27. 		int r = idx * 2 + 2;
  28. 		int mid = (a + b) / 2;
  29. 		add(l, a, mid, pos, val);
  30. 		add(r, mid+1, b, pos, val);
  31. 		sum[idx] = sum[l] + sum[r];
  32. 		minPrefix[idx] = min(minPrefix[l], sum[l] + minPrefix[r]);
  33. 	}
  34. }
  35.  
  36. int main()
  37. {
  38. 	rint(N);
  39. 	int arr[N];
  40. 	ji(N) rint(arr[i]);
  41. 	int ans = 0;
  42. 	ji(N / 2)
  43. 	{
  44. 		add(0, 1, N, arr[i * 2],     +1);
  45. 		add(0, 1, N, arr[i * 2 + 1], +1);
  46. 		add(0, 1, N, arr[i],         -2);
  47. 		if (minPrefix[0] == 0)
  48. 			ans = i + 1;
  49. 	}
  50. 	printf("%d\n", ans);
  51. }
  52.  
Success #stdin #stdout 0s 6268KB
comments (?)
stdin
copy 
6
3 5 4 2 1 6
stdout
copy 
2
https://ideone.com/1vT6q7
language:
C++14 (gcc 8.3)
created:
8 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!