fork download
copy 
  1. #include <iostream>
  2. #include <string.h>
  3. using namespace std;
  4.  
  5. long long int segT[1200000];
  6. int R=262143;
  7. long long int ans;
  8. void fSet(int no,int p1,int l2,int r2,long long int num){
  9. 	if(r2<p1 || p1<l2)return ;
  10. 	if(l2==r2){
  11. 		segT[no]=num;
  12. 		return ;
  13. 	}
  14. 	int m=(l2+r2)/2;
  15. 	if(l2<=p1 && p1<=m){
  16. 		fSet(no*2+1,p1,l2,m,num);
  17. 	}else{
  18. 		fSet(no*2+2,p1,m+1,r2,num);
  19. 	}
  20. 	return ;
  21. }
  22. long long int fAdd(int no,int p1,int l2,int r2,long long int add){
  23. 	if(r2<p1 || p1<l2)return segT[no];
  24.  
  25. 	if(l2==r2){
  26. 		segT[no]+=add;
  27. 		return segT[no];
  28. 	}
  29. 	int m=(l2+r2)/2;
  30. 	long long int res1=-1;
  31. 	long long int res2=-1;
  32. 	if(l2<=p1 && p1<=m){
  33. 		res1=fAdd(no*2+1,p1,l2,m,add);
  34. 		res2=segT[no*2+2];
  35. 	}else{
  36. 		res1=segT[no*2+1];
  37. 		res2=fAdd(no*2+2,p1,m+1,r2,add);
  38. 	}
  39. 	if(res1==-1 || res2==-1){
  40. 		segT[no]=-1;
  41. 	}else if(res1==res2){
  42. 		segT[no]=res1;
  43. 	}else{
  44. 		segT[no]=-1;
  45. 	}
  46. 	return segT[no];
  47. }
  48. long long int fCheck(int no,int l,int r,int l2,int r2,long long int resA){
  49. 	if(r2<l || r<l2)return resA;
  50. 	if(l2==r2){
  51.  
  52. 		if(ans==-2){
  53. 			ans=segT[no];
  54. 		}else if(ans!=segT[no]){
  55. 			ans=-1;
  56. 		}
  57. 		//cout<<"("<<no<<" "<<ans<<","<<l2<<","<<r2<<","<<segT[no]<<")"<<endl;
  58. 		return segT[no];
  59. 	}
  60. 	if(l<=l2 && r2<=r){
  61.  
  62. 		if(ans==-2){
  63. 			ans=segT[no];
  64. 		}else if(ans!=segT[no]){
  65. 			ans=-1;
  66. 		}
  67. 		//cout<<no<<" "<<ans<<"("<<l2<<","<<r2<<","<<segT[no]<<")"<<endl;
  68. 		return segT[no];
  69. 	}else{
  70. 		int m=(l2+r2)/2;
  71. 		long long int res1=fCheck(no*2+1,l,r,l2,m,segT[no*2+2]);
  72. 		long long int res2=fCheck(no*2+2,l,r,m+1,r2,segT[no*2+1]);
  73. 		if(res1==-1 || res2==-1){
  74. 			return -1;
  75. 		}else if(res1==res2){
  76. 			return res1;
  77. 		}else{
  78. 			return -1;
  79. 		}
  80. 	}
  81. }
  82.  
  83.  
  84.  
  85. int main() {
  86. 	int n,m;
  87. 	cin>>n>>m;
  88. 	memset(segT,-1,sizeof(segT));
  89. 	for(int i=0;i<n;i++){
  90. 		long long int num;
  91. 		cin>>num;
  92. 		fSet(0,i,0,R,num);
  93. 	}
  94. 	for(int i=0;i<n;i++){
  95. 		fAdd(0,i,0,R,0);
  96. 	}
  97.  
  98. 	for(int i=0;i<m;i++){
  99. 		int c1;
  100. 		cin>>c1;
  101. 		if(c1==1){
  102. 			int p1,add;
  103. 			cin>>p1>>add;
  104. 			p1--;
  105. 			fAdd(0,p1,0,R,add);
  106. 		}else{
  107. 			int l,r;
  108. 			cin>>l>>r;
  109. 			l--;
  110. 			r--;
  111. 			ans=-2;
  112. 			fCheck(0,l,r,0,R,segT[0]);
  113. 			if(ans==-1){
  114. 				cout<<"No"<<endl;
  115. 			}else{
  116. 				cout<<"Yes"<<endl;
  117. 			}
  118. 		}
  119. 		//for(int i=0;i<15;i++){
  120. 		//	cout<<"("<<i<<","<<segT[i]<<")";
  121. 		//}
  122. 		//cout<<endl;
  123. 	}
  124.  
  125. 	return 0;
  126. }
Success #stdin #stdout 0.01s 12916KB
comments (?)
stdin
copy 
7 8
1 2 3 3 10 1 1
2 1 3
2 6 7
1 5 1
1 4 8
2 3 5
1 3 8
2 4 5
2 1 1
stdout
copy 
No
Yes
No
Yes
Yes
https://ideone.com/Fd8f2Z
language:
C++ (gcc 8.3)
created:
1 day 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!