fork(5) download
copy 
  1. #include<iostream>
  2. #include<string>
  3. #include<deque>
  4.  
  5. using namespace std;
  6.  
  7. int a[1000001], n;
  8. long long int ans = 0;
  9. string s;
  10. int k;
  11.  
  12. int bn_find_first_max_right(int l, int r, long long int x)
  13. {
  14. 	int vt = -1;
  15. 	while (l <= r)
  16. 	{
  17. 		int mid = (l + r) / 2;
  18. 		if (a[mid] == x)
  19. 		{
  20. 			vt = mid;
  21. 			l = mid + 1;
  22. 		}
  23. 		else if (a[mid] > x)
  24. 			r = mid - 1;
  25. 		else if (a[mid] < x)
  26. 			l = mid + 1;
  27. 	}
  28. 	return vt;
  29. }
  30. int bn_find_first_max_left(int l, int r, long long int x)
  31. {
  32. 	int vt = -1;
  33. 	while (l <= r)
  34. 	{
  35. 		int mid = (l + r) / 2;
  36. 		if (a[mid] == x)
  37. 		{
  38. 			vt = mid;
  39. 			r = mid - 1;
  40. 		}
  41. 		else if (a[mid] > x)
  42. 			r = mid - 1;
  43. 		else if (a[mid] < x)
  44. 			l = mid + 1;
  45. 	}
  46. 	return vt;
  47. }
  48.  
  49. void inp()
  50. {
  51. 	cin >> k;
  52. 	cin.ignore();
  53. 	getline(cin, s);
  54. 	n = s.size();
  55. 	s = 'x' + s;
  56. 	for (int i = 1; i <= n; i++)
  57. 		a[i] = a[i - 1] + (s[i] - '0');
  58.  
  59. }
  60. void xuli()
  61. {
  62. 	for(int i = 1; i <= n; i++)
  63. 		if (a[i] >= k)
  64. 		{
  65. 			int left = bn_find_first_max_left(0, i - 1, a[i] - k);
  66. 			int right = bn_find_first_max_right(0, i - 1, a[i] - k);
  67. 			if(left != - 1 && right != -1)
  68. 				ans += right - left + 1;
  69. 		}	
  70. 	cout << ans;
  71. }
  72. int main()
  73. {
  74. 	inp();
  75. 	xuli();
  76. }
  77.  
Success #stdin #stdout 0.01s 5392KB
comments (?)
stdin
copy 
100
01010
stdout
copy 
Standard output is empty
https://ideone.com/bEz2W8
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!