fork download
copy 
  1. //This solution is wrong at 75 test case
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define ll long long
  5.  
  6. // build tree
  7. ll tree[400001]={0};
  8. void build_tree(ll int *a, ll int s,ll int e, ll int *tree, ll int index)
  9. {
  10. 	if(s==e)
  11. 	{
  12. 		tree[index] = a[s];
  13. 		return;
  14. 	}
  15. 	ll int mid = (s+e)/2;
  16. 	build_tree(a,s,mid,tree,2*index);
  17. 	build_tree(a,mid+1,e,tree,2*index+1);
  18. 	tree[index] = min(tree[2*index],tree[2*index+1]);
  19. 	return;
  20. }
  21. ll query(ll int *tree,ll int ss,ll int se,ll int qs,ll int qe ,ll int index)
  22. {
  23. 	//complete overlap
  24. 	if(ss>=qs and se<=qe)
  25. 	{
  26. 		return tree[index];
  27. 	}
  28. 	//No Overlap
  29. 	if(qe<ss || qs>se)
  30. 	return INT_MAX;
  31.  
  32. 	//partial overlap
  33. 	ll int mid = (ss + se)/2;
  34. 	ll int left = query(tree,ss,mid,qs,qe,2*index);
  35. 	ll int right = query(tree,mid+1,se,qs,qe,2*index+1);
  36. 	return min(left,right);
  37. }
  38. //point update
  39. void point_update(ll int *tree, ll int ss,ll int se, ll int i,ll int inc,ll int index)
  40. {
  41. 	if(i>se || i<ss)
  42. 	return;
  43. 	if(ss == se)
  44. 	{
  45. 		tree[index] = inc;
  46. 		return;
  47. 	}
  48. 	ll int mid = (ss + se)/2;
  49. 	point_update(tree,ss,mid,i,inc,2*index);
  50. 	point_update(tree,mid+1,se,i,inc,2*index+1);
  51. 	tree[index] = min(tree[2*index],tree[2*index+1]);
  52. 	return;
  53. }
  54.  
  55. ll count_mini(ll int *tree,ll int ss,ll int se,ll int qs,ll int qe ,ll num,ll int index)
  56. {
  57. 	if(qe<ss || qs>se)
  58. 	return 0;
  59. 	if((se<=qe && ss>=qs)&&tree[index]!=num)
  60. 	return 0;
  61. 	if((se<=qe || ss>=qs)&&tree[index]>num)
  62. 	return 0;
  63. 	if(ss == se )
  64. 	{
  65. 		if(tree[index]==num)
  66. 		return 1;
  67. 		else
  68. 		return 0;
  69. 	}
  70. 	 ll int mid = (ss + se)/2;
  71. 	 ll left =  count_mini(tree,ss,mid,qs,qe,num,2*index);
  72. 	 ll right = count_mini(tree,mid+1,se,qs,qe,num,2*index+1);
  73. 	 return left+right;
  74. }
  75.  
  76. void solve()
  77. {
  78. 	int n,q;
  79. 	cin>>n>>q;
  80.  
  81. 	ll a[n];
  82. 	for(int i=0;i<n;i++)
  83. 	cin>>a[i];
  84.  
  85. 	build_tree(a,0,n-1,tree,1);
  86. 	// for(int i=1;i<=4*n;i++)
  87. 	// cout<<tree[i]<<endl;
  88.  
  89. 	while(q--)
  90. 	{
  91. 		ll num,l,r;
  92. 		cin>>num>>l>>r;
  93. 		if(num==1)
  94. 		{
  95. 			point_update(tree,0,n-1,l,r,1);
  96. 		}
  97. 		else
  98. 		{
  99. 			ll int num1 = query(tree,0,n-1,l,r-1,1);
  100. 			ll int num2 = count_mini(tree,0,n-1,l,r-1,num1,1);
  101. 			cout<<num1<<" "<<num2<<endl;
  102. 		}
  103.  
  104. 	}
  105.  
  106. }
  107. int main()
  108. {
  109. 	ios_base::sync_with_stdio(false); 
  110.     	cin.tie(NULL); 
  111.  
  112.  
  113.     ll int t=1;
  114. 	 // cin>>t;
  115. 	while(t--)
  116. 	{  
  117.       solve();
  118.     }
  119.  
  120. 	return 0;
  121. }	
  122.  
Time limit exceeded #stdin #stdout 5s 4796KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/AxLahq
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!