fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int maxN = 1e6+5;
  4.  
  5. int n, k, a[maxN], b[maxN], c[maxN], p[maxN], sum[3][maxN], suff[3][maxN], ans = 0, x=-1;
  6.  
  7. // void dnc(int L, int R, int turn)
  8. // {
  9. // 	if(L >= R) return;
  10. // 	int target = 1-x;
  11. // 	if(turn % 2 == 1) target = x;
  12. // 	int left = L, right = R, res1 = -1;
  13. // 	while(left <= right)
  14. // 	{
  15. // 		int mid = (left + right)/2;
  16. // 		if(sum[target][mid] >= sum[target][L-1]+1)
  17. // 		{
  18. // 			res1 = mid;
  19. // 			right = mid-1;
  20. // 		}
  21. // 		else left = mid+1;
  22. // 	}
  23. // 	left = L, right = R;
  24. // 	int res2 = -1;
  25. // 	while(left <= right)
  26. // 	{
  27. // 		int mid = (left + right)/2;
  28. // 		if(suff[target][mid] >= suff[target][R+1]+1)
  29. // 		{
  30. // 			res2 = mid;
  31. // 			left = mid+1;
  32. // 		}
  33. // 		else right = mid-1;
  34. // 	}
  35. // 	left = res1+1, right = R;
  36. // 	int res3 = -1;
  37. // 	while(left <= right)
  38. // 	{
  39. // 		int mid = (left + right)/2;
  40. // 		if(sum[target][mid] >= sum[target][res1+1-1]+1)
  41. // 		{
  42. // 			res3 = mid;
  43. // 			right = mid-1;
  44. // 		}
  45. // 		else left = mid+1;
  46. // 	}
  47. // 	if(res1 == res2)
  48. // 	cout<<res1<<" "<<res3<<" "<<res2<<'\n';
  49. // 	return;
  50. // }
  51.  
  52. void solve()
  53. {
  54. 	int end1 = -1, end2 = -1;
  55. 	for(int i=1; i<=n; i+=1)
  56. 	{
  57. 		sum[0][i] = sum[0][i-1];
  58. 		sum[1][i] = sum[1][i-1];
  59. 		if(a[i] == 0) sum[0][i]++;
  60. 		else sum[1][i]++;
  61. 	}
  62. 	for(int i=n; i>=1; i-=1)
  63. 	{
  64. 		suff[0][i] = suff[0][i+1];
  65. 		suff[1][i] = suff[1][i+1];
  66. 		if(a[i] == 0) suff[0][i]++;
  67. 		else suff[1][i]++;
  68. 	}
  69. 	// cout<<suff[1][9]<<'\n';
  70. 	// for(int i=1; i<=n; i+=1) cout<<suff[1][i]<<" "; cout<<'\n';
  71. 	// dnc(1, n, 0);
  72. }
  73.  
  74. int main() {
  75. 	int test = 1;
  76. 	cin>>test;
  77. 	while(test--)
  78. 	{
  79. 		int n1, k1, dem = 1;
  80. 		cin>>n1>>k1;
  81. 		ans = n = k = 0;
  82. 		for(int i=0; i<=n1+1; i+=1) sum[0][i] = sum[1][i] = suff[0][i] = suff[1][i], p[i] = 0, b[i] = 0, c[i] = 0;
  83. 		a[0] = -1;
  84. 		for(int i=1; i<=n1; i+=1)
  85. 		{
  86. 			int tmp; cin>>tmp;
  87. 			if(tmp != a[dem-1]) a[dem] = tmp, n++, dem++;
  88. 			b[i] = n;
  89. 		}
  90. 		dem = 1;
  91. 		for(int i=1; i<=k1; i+=1)
  92. 		{
  93. 			int tmp; cin>>tmp;
  94. 			int actual = b[tmp];
  95. 			if(c[actual] != 1) p[dem] = actual, c[actual] = 1, k++, dem++;
  96. 		}
  97. 		x = a[p[1]];
  98. 		int end1 = 0, end2 = 0;
  99. 		for(int i=1; i<=n; i+=1)
  100. 		{
  101. 			if(a[i] != x)
  102. 			{
  103. 				end1 = i; break;
  104. 			}
  105. 		}
  106. 		for(int i=n; i>=1; i-=1)
  107. 		{
  108. 			if(a[i] != x)
  109. 			{
  110. 				end2 = i; break;
  111. 			}
  112. 		}
  113. 		if(end2 == 0)
  114. 		{
  115. 			cout<<0<<'\n';
  116. 		}
  117. 		else
  118. 		{
  119. 			int tmp = (end2-end1+1);
  120. 			int ans = (tmp/2) + 1;
  121. 			cout<<end1<<" "<<end2<<'\n';
  122. 		}
  123. 		// solve();
  124. 	}
  125. 	return 0;
  126. }
Success #stdin #stdout 0.01s 16008KB
comments (?)
stdin
copy 
6
2 1
1 0
1
3 2
0 1 0
1 3
5 5
1 1 1 1 1
1 2 3 4 5
9 5
0 1 0 0 1 0 0 1 0
3 4 6 7 9
13 4
1 0 0 1 0 1 0 1 1 0 1 0 1
4 8 11 13
15 3
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
3 11 13
stdout
copy 
2 2
2 2
0
2 6
2 10
2 14
https://ideone.com/ZAsYoH
language:
C++ (gcc 8.3)
created:
4 hours 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!