fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define MAX 1000007
  6. #define INF 1000000000000000LL
  7. #define MOD 1000000007
  8. #define sd(x) scanf("%d",&x)
  9. #define sll(x) scanf("%lld",&x)
  10. #define PB push_back
  11. #define F first
  12. #define S second
  13. #define rep(i,a,b) for(int i = a; i < b; ++i)
  14. #define dd double
  15. #define PI 3.14159265358979323846
  16.  
  17. ll n;
  18. ll A[MAX];
  19. ll B[MAX];
  20. ll x;
  21. int main(int argc, char const *argv[])
  22. {
  23. 	// freopen("input.txt", "r" , stdin);
  24. 	// freopen("output.txt", "w", stdout);
  25. 	memset(	A, 0, sizeof A);
  26. 	memset(B, 0, sizeof B);
  27. 	ios_base::sync_with_stdio(false);
  28. 	cin.tie(NULL);cout.tie(NULL);
  29.  
  30. 	cin>>n;
  31. 	rep(i,1,n+1)
  32. 	{
  33. 		cin>>x;
  34. 		int y = __builtin_popcount(x);
  35. 		A[i] = y;
  36. 		B[i] = y;
  37. 	}
  38. 	if(n == 1)
  39. 	{
  40. 		cout<<0<<endl;
  41. 		return 0;	
  42. 	}
  43.  
  44. 	rep(i,2,n+1)
  45. 		A[i] += A[i-1];
  46.  
  47. 	ll res = 0;
  48. 	ll odd = 0, even = 0;
  49.  
  50. 	rep(i,1,n+1)
  51. 	{
  52. 		if(A[i]&1)
  53. 		{
  54. 			++odd;
  55. 			if(odd > 1)
  56. 			{
  57. 				res += odd;
  58. 				ll maxm;
  59. 				for(int j = i; j > (i-66, 0); --j)
  60. 				{
  61. 					maxm = max(maxm, B[j]);
  62. 					if(A[j-1]%2 == 1 and (maxm > (A[i]- A[j-1])/2))
  63. 						--res;
  64. 				}
  65. 			}
  66.  
  67. 		}
  68. 		else
  69. 		{
  70. 			++even;
  71. 			if(even > 1)
  72. 			{
  73. 				res += even;
  74. 				ll maxm;
  75. 				for(int j = i; j > (i-66, 0); --j)
  76. 				{
  77. 					maxm = max(maxm, B[j]);
  78. 					if(A[j-1]%2 == 0 and (maxm > (A[i]- A[j-1])/2))
  79. 						--res;
  80. 				}
  81. 			}
  82. 		}
  83. 	}
  84.  
  85.  
  86. 	cout<<res<<endl;
  87.  
  88. 	return 0;
  89. }
Success #stdin #stdout 0s 30856KB
comments (?)
stdin
copy 
3
6 7 14
stdout
copy 
2
https://ideone.com/iiTZkx
language:
C++14 (gcc 8.3)
created:
5 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!