fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int MAXN = 1000005;
  4. const int B = 1005;
  5. using pi = pair<int, int>;
  6.  
  7. int n, q, a[MAXN];
  8.  
  9. int nxt[MAXN];
  10.  
  11. struct query{ int t, x, y, z; };
  12. bool upd[MAXN];
  13.  
  14. void Batch(vector<query> &Q){
  15. 	vector<int> v;
  16. 	int idx = 0;
  17. 	for(auto &i : Q){
  18. 		if(i.t == 1){
  19. 			v.push_back(i.x);
  20. 			v.push_back(i.x + 1);
  21. 			upd[i.x] = 1;
  22. 		}
  23. 		else{
  24. 			v.push_back(i.x);
  25. 			v.push_back(i.y);
  26. 		}
  27. 		idx++;
  28. 	}
  29. 	sort(v.begin(), v.end());
  30. 	v.resize(unique(v.begin(), v.end()) - v.begin());
  31. 	for(int i=0; i<v.size()-1; i++){
  32. 		if(upd[v[i]]){
  33. 			for(auto &j : Q){
  34. 				if(j.t == 1){
  35. 					if(j.x == v[i]){
  36. 						a[j.x] = j.y;
  37. 					}
  38. 					continue;
  39. 				}
  40. 				if(j.x <= v[i] && j.y >= v[i] + 1 && j.z == a[v[i]]){
  41. 					j.z++;
  42. 				}
  43. 			}
  44. 			upd[v[i]] = 0;
  45. 		}
  46. 		else{
  47. 			for(int j=v[i+1]-1; j>=v[i]; j--){
  48. 				nxt[a[j]] = nxt[a[j] + 1] + 1;
  49. 			}
  50. 			for(auto &j : Q){
  51. 				if(j.t == 2 && j.x <= v[i] && j.y >= v[i+1]){
  52. 					j.z += nxt[j.z];
  53. 				}
  54. 			}
  55. 			for(int j=v[i]; j<v[i+1]; j++) nxt[a[j]] = 0;
  56. 		}
  57. 	}
  58. 	for(auto &i : Q){
  59. 		if(i.t == 2) printf("%d\n", i.z - 1);
  60. 	}
  61. 	Q.clear();
  62. }
  63.  
  64. namespace FIO{
  65. 	static char buf[1<<19];
  66. 	static int idx = 0;
  67. 	static int bytes = 0;
  68. 	static inline int _read(){
  69. 		if(!bytes || idx == bytes){
  70. 			bytes = (int)fread(buf, sizeof(buf[0]), sizeof(buf), stdin);
  71. 			idx = 0;
  72. 		}
  73. 		return buf[idx++];
  74. 	}
  75. 	static inline int _readInt(){
  76. 		int x = 0, s = 1;
  77. 		int c = _read();
  78. 		while(c <= 32) c = _read();
  79. 		if(c == '-') s = -1, c = _read();
  80. 		while(c > 32){
  81. 			x = 10 * x + (c - '0');
  82. 			c = _read();
  83. 		}
  84. 		if(s < 0) x = -x;
  85. 		return x;
  86. 	}
  87. }
  88.  
  89. int main(){
  90. 	vector<query> qry;
  91. 	n = FIO::_readInt();
  92. 	q = FIO::_readInt();
  93. 	for(int i=0; i<n; i++){
  94. 		a[i] = FIO::_readInt();
  95. 	}
  96. 	while(q--){
  97. 		int t = FIO::_readInt();
  98. 		if(t == 1){
  99. 			int x, y;
  100. 			x = FIO::_readInt();
  101. 			y = FIO::_readInt();
  102. 			qry.push_back({1, x, y});
  103. 		}
  104. 		else{
  105. 			int l, r, k;
  106. 			l = FIO::_readInt();
  107. 			r = FIO::_readInt();
  108. 			k = FIO::_readInt();
  109. 			qry.push_back({2, l, r, k});
  110. 		}
  111. 		if(qry.size() > B){
  112. 			Batch(qry);
  113. 		}
  114. 	}
  115. 	Batch(qry);
  116. }
Time limit exceeded #stdin #stdout 5s 24544KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/GmssvS
language:
C++14 (gcc 8.3)
created:
5 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!