fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Numeric Constants
  5. #define N 1000000007
  6. #define maxs 100005
  7. #define mins 505
  8. #define eps 0.000000000001
  9. #define imax 2000000200
  10. #define llmax 1000000002000000000ll
  11. #define pi 3.141592653589793
  12.  
  13. // Others
  14. #define ll long long
  15. #define pb push_back
  16. #define gc getchar_unlocked
  17. #define iosbase ios_base::sync_with_stdio(false)
  18. #define pii pair<int,int>
  19. #define pll pair<ll,ll>
  20. #define ppi pair<pair<int,int>,int>
  21. #define ppl pair<pll,ll>
  22. #define vi vector<int>
  23. #define sc scanf
  24. #define pr printf
  25. #define lld I64d
  26. #define F first
  27. #define S second
  28. #define siter set<int>::iterator
  29. #define p_pq priority_queue
  30. #define ub upper_bound
  31. #define lb lower_bound
  32.  
  33. int rotation[mins],freq[mins][maxs],a[maxs];
  34.  
  35. int main()
  36. {
  37. 	int n,q,l,r,sblock,endblock,ans,type,x,i,noblocks,blsize,j;
  38. 	sc("%d %d",&n,&q);
  39. 	for(i=0;i<n;i++){
  40. 		sc("%d",&a[i]);
  41. 	}
  42. 	blsize=sqrt(n);
  43. 	noblocks=ceil((double)n/blsize);
  44. 	for(i=0;i<noblocks;i++){
  45. 		for(j=i*blsize;j<min((i+1)*blsize,n);j++){
  46. 			freq[i][a[j]]++;
  47. 		}
  48. 	}
  49. 	while(q--){
  50. 		sc("%d %d %d %d",&type,&l,&r,&x);
  51. 		if(type==2){
  52. 			sblock=l/blsize;
  53. 			endblock=r/blsize;
  54. 			if(sblock==endblock){
  55. 				ans=0;
  56. 				for(i=l;i<=r;i++){
  57. 					if(((x-rotation[sblock]+n)%n)==a[i]){
  58. 						ans++;
  59. 					}
  60. 				}
  61. 			}
  62. 			else{
  63. 				ans=0;
  64. 				for(i=l;i<(sblock+1)*blsize;i++){
  65. 					if(((x-rotation[sblock]+n)%n)==a[i]){
  66. 						ans++;
  67. 					}
  68. 				}
  69. 				for(i=endblock*blsize;i<=r;i++){
  70. 					if(((x-rotation[endblock]+n)%n)==a[i]){
  71. 						ans++;
  72. 					}
  73. 				}
  74. 				for(i=sblock+1;i<=endblock-1;i++){
  75. 					ans+=freq[i][(x-rotation[i]+n)%n];
  76. 				}
  77. 			}
  78. 			pr("%d\n",ans);
  79. 		}
  80. 		else{
  81. 			sblock=l/blsize;
  82. 			endblock=r/blsize;
  83. 			if(sblock==endblock){
  84. 				ans=0;
  85. 				for(i=l;i<=r;i++){
  86. 					freq[sblock][a[i]]--;
  87. 					a[i]=(a[i]+x)%n;
  88. 					freq[sblock][a[i]]++;
  89. 				}
  90. 			}
  91. 			else{
  92. 				ans=0;
  93. 				for(i=l;i<(sblock+1)*blsize;i++){
  94. 					freq[sblock][a[i]]--;
  95. 					a[i]=(a[i]+x)%n;
  96. 					freq[sblock][a[i]]++;
  97. 				}
  98. 				for(i=endblock*blsize;i<=r;i++){
  99. 					freq[endblock][a[i]]--;
  100. 					a[i]=(a[i]+x)%n;
  101. 					freq[endblock][a[i]]++;
  102. 				}
  103. 				for(i=sblock+1;i<=endblock-1;i++){
  104. 					rotation[i]=(rotation[i]+x)%n;
  105. 				}
  106. 			}
  107. 		}
  108. 	}
  109. 	return 0;
  110. }
Time limit exceeded #stdin #stdout 5s 201152KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/PBgA0a
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!