fork download
copy 
  1.  
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define ll long long
  5.  
  6. ll gb=-1;
  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] = max(tree[2*index],tree[2*index+1]);
  18. 	return;
  19. }
  20. void query(ll int *tree,ll int ss,ll int se,ll x ,ll l ,ll int index)
  21. {
  22. 	//complete overlap
  23.  
  24. 	if(tree[index]<x)
  25. 	return;
  26. 	if(gb>=0||se<l)   // just add one extra condition as compare to "First element at least X" (previous problem)
  27. 	return;
  28. 	if(ss==se)
  29. 	{
  30. 		if(tree[index]>=x)
  31. 		gb=ss;
  32. 		return;
  33. 	}
  34. 	ll int mid = (ss + se)/2;
  35. 	 query(tree,ss,mid,x,l,2*index);
  36. 	 query(tree,mid+1,se,x,l,2*index+1);
  37. 	 return;
  38.  
  39. }
  40. //point update
  41. void point_update(ll int *tree, ll int ss,ll int se, ll int i,ll int inc,ll int index)
  42. {
  43. 	if(i>se || i<ss)
  44. 	return;
  45. 	if(ss == se)
  46. 	{
  47. 		tree[index] = inc;
  48. 		return;
  49. 	}
  50. 	ll int mid = (ss + se)/2;
  51. 	point_update(tree,ss,mid,i,inc,2*index);
  52. 	point_update(tree,mid+1,se,i,inc,2*index+1);
  53. 	tree[index] = max(tree[2*index],tree[2*index+1]);
  54. 	return;
  55. }
  56.  
  57. void solve()
  58. {
  59. 	int n,q;
  60. 	cin>>n>>q;
  61.  
  62. 	ll a[n];
  63. 	for(int i=0;i<n;i++)
  64. 	cin>>a[i];
  65. 	ll tree[4*n+1]={0};
  66. 	build_tree(a,0,n-1,tree,1);
  67.  
  68. 	while(q--)
  69. 	{
  70. 		ll num,l,r;
  71. 		cin>>num>>l>>r;
  72. 		if(num==1)
  73. 		{
  74. 			point_update(tree,0,n-1,l,r,1);
  75.  
  76. 		}
  77. 		else
  78. 		{
  79. 			gb=-1;
  80. 			query(tree,0,n-1,l,r,1);
  81. 			cout<<gb<<endl;
  82. 		}
  83.  
  84. 	}
  85.  
  86. }
  87. int main()
  88. {
  89. 	ios_base::sync_with_stdio(false); 
  90.     	cin.tie(NULL); 
  91.  
  92.     // int src[101]={0};
  93.     // int dest[101]={0};
  94.  
  95.     ll int t=1;
  96. 	 // cin>>t;
  97. 	while(t--)
  98. 	{  
  99.       solve();
  100.     }
  101.  
  102. return 0;
  103. }
  104.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp:65: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/pRKg0J
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!