fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long int
  3. #define inf 1e18
  4. #define iosbase ios_base::sync_with_stdio(false);
  5. #define mp make_pair
  6. #define pb push_back
  7. #define MOD 1000000007
  8. #define sc(n) scanf("%d" , &n);
  9. #define Max 100005
  10. using namespace std;
  11. typedef vector<ll> VI;
  12. typedef map<ll , ll> MI;
  13. int arr[Max],totalBlocks, k, seg[505][Max] , displace[505];
  14.  
  15.  
  16. void create(int k , int n){
  17. 	for(int i=0 ; i<n ; i++){
  18. 		seg[i/k][arr[i]]++;
  19. 	}
  20. }
  21.  
  22. void update(int k , int low , int high , int x , int n){
  23.  
  24. 	int ind = low;
  25.  
  26. 	while((ind)%k!=0 && ind<=high){
  27. 		seg[ind/k][arr[ind]]--;
  28. 		arr[ind]= (arr[ind]+x)%n;
  29. 		seg[ind/k][arr[ind]]++;
  30. 		ind++;
  31. 	}
  32. 	while(ind+k <= high){
  33. 		displace[ind/k] = (displace[ind/k]+x)%n;
  34. 		ind+=k;
  35. 	}
  36. 	while(ind<=high){
  37. 		seg[ind/k][arr[ind]]--;
  38. 		arr[ind]= (arr[ind]+x)%n;
  39. 		seg[ind/k][arr[ind]]++;
  40. 		ind++;
  41. 	}
  42.  
  43. }
  44.  
  45. int query(int k , int low , int high ,int x , int n){
  46.  
  47. 	int ind = low;
  48. 	int ans=0;
  49.  
  50. 	while((ind)%k!=0 && ind<=high){
  51. 		if( (arr[ind] + displace[ind/k])%n == x )ans++;
  52. 		ind++;
  53. 	}
  54. 	while(ind+k <= high){
  55. 		ans+= seg[ind/k][ (x-displace[ind/k] + n)%n ];
  56. 		ind+=k;
  57. 	}
  58. 	while(ind<=high){
  59. 		if( (arr[ind] + displace[ind/k])%n == x )ans++;
  60. 		ind++;
  61. 	}
  62. 	return ans;
  63. }
  64.  
  65.  
  66. int main()
  67. {
  68. 	int n,q,a,low,hi,x;
  69. 	sc(n);sc(q);
  70.  
  71. 	for(int i=0 ; i<n ; i++){
  72. 		sc(arr[i]);
  73. 	}
  74.  
  75. 	k = sqrt(n);
  76. 	totalBlocks = ceil((double)n/k);
  77.  
  78. 	create(k,n);
  79.  
  80. 	while(q--)
  81. 	{
  82. 		sc(a);
  83. 		if(a==1){
  84.  
  85. 			//update part
  86. 			sc(low);sc(hi);sc(x);
  87. 			update(k,low,hi,x,n);
  88. 		}
  89. 		else{
  90.  
  91. 			//query part
  92. 			sc(low);sc(hi);sc(x);
  93. 			int ans = query(k,low,hi,x,n);
  94. 			printf("%d\n",ans);
  95. 		}
  96. 	}
  97.  
  98.  
  99. 	return 0;
  100. }
Time limit exceeded #stdin #stdout 5s 201152KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/2AmIhZ
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!