fork download
copy 
  1.  
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define ll long long
  5.  
  6. ll glb;
  7. void build_tree(ll int *a, ll int s,ll int e, ll int *tree, ll int index)
  8. {
  9. 	if(s==e)
  10. 	{
  11. 		tree[index] = a[s];
  12. 		return;
  13. 	}
  14. 	ll int mid = (s+e)/2;
  15. 	build_tree(a,s,mid,tree,2*index);
  16. 	build_tree(a,mid+1,e,tree,2*index+1);
  17. 	tree[index] += tree[2*index]+tree[2*index+1];
  18. 	return;
  19. }
  20.  
  21. ll query(ll *tree,ll ss,ll se,ll & k ,ll index)
  22. {
  23. 	if(glb!=-1||tree[index]==0)
  24. 	return INT_MAX;
  25.  
  26. 	if(tree[index]<k)
  27. 	{
  28. 		k -= tree[index];
  29. 		return INT_MAX;
  30. 	}
  31. 	if(ss == se)
  32. 	{
  33. 		glb = ss;
  34. 		return ss;
  35. 	}
  36. 	//partial overlap
  37. 	ll int mid = (ss + se)/2;
  38. 	ll int left = query(tree,ss,mid,k,2*index);
  39. 	ll int right = query(tree,mid+1,se,k,2*index+1);
  40. 	return min(left,right);
  41. }
  42. //point update
  43. void point_update(ll  *tree, ll ss,ll se, ll i,ll inc,ll index)
  44. {
  45. 	if(i>se || i<ss)
  46. 	return;
  47. 	if(ss == se)
  48. 	{
  49. 		tree[index] = inc;
  50. 		return;
  51. 	}
  52. 	ll int mid = (ss + se)/2;
  53. 	point_update(tree,ss,mid,i,inc,2*index);
  54. 	point_update(tree,mid+1,se,i,inc,2*index+1);
  55. 	tree[index] = tree[2*index]+tree[2*index+1];
  56. 	return;
  57. }
  58. void solve()
  59. {
  60. 	int n,q;
  61. 	cin>>n>>q;
  62.  
  63. 	ll a[n];
  64. 	for(int i=0;i<n;i++)
  65. 	cin>>a[i];
  66. 	ll tree[4*n+1]={0};
  67.  
  68. 	build_tree(a,0,n-1,tree,1);
  69.  
  70. 	// for(int i=1;i<=4*n;i++)
  71. 	// cout<<tree[i]<<endl;
  72.  
  73. 	while(q--)
  74. 	{
  75. 		ll num,l;
  76. 		cin>>num>>l;
  77. 		if(num==1)
  78. 		{
  79. 			point_update(tree,0,n-1,l,!a[l],1);
  80. 			a[l]=!a[l];
  81. 		}
  82. 		else
  83. 		{
  84. 		l++;
  85. 		glb=-1;
  86. 		ll x = query(tree,0,n-1,l,1);
  87. 		cout<<x<<endl;
  88. 		}
  89.  
  90. 	}
  91.  
  92. }
  93. int main()
  94. {
  95. 	ios_base::sync_with_stdio(false); 
  96.     	cin.tie(NULL); 
  97.  
  98.  
  99.     ll int t=1;
  100. 	 // cin>>t;
  101. 	while(t--)
  102. 	{  
  103.       solve();
  104.     }
  105.  
  106. return 0;
  107. }
  108.  
  109.  
  110.  
  111.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp:66:10: error: variable-sized object may not be initialized
        ll tree[4*n+1]={0};
                ^~~~~
1 error generated.
stdout
copy 
Standard output is empty
https://ideone.com/mrNn1C
language:
C++14 (clang 8.0)
created:
4 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!