fork download
copy 
  1. // iostream is too mainstream
  2. #include <cstdio>
  3. // bitch please
  4. #include <iostream>
  5. #include <algorithm>
  6. #include <cstdlib>
  7. #include <vector>
  8. #include <set>
  9. #include <map>
  10. #include <queue>
  11. #include <stack>
  12. #include <list>
  13. #include <cmath>
  14. #include <iomanip>
  15. #define dibs reserve
  16. #define OVER9000 1234567890
  17. #define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
  18. #define tisic 47
  19. #define soclose 1e-8
  20. #define chocolate win
  21. // so much chocolate
  22. #define patkan 9
  23. #define ff first
  24. #define ss second
  25. #define abs(x) ((x < 0)?-(x):x)
  26. #define uint unsigned int
  27. #define dbl long double
  28. using namespace std;
  29. // mylittledoge
  30.  
  31. struct node {
  32. 	int son[2];
  33. 	int z,k,pok,free;
  34. };
  35.  
  36. struct intervalac {
  37. 	vector<node> T;
  38.  
  39. 	void constI(int akt) {
  40. 		node n =T[akt];
  41. 		T[akt].free =n.k-n.z;
  42. 		if(n.z+1 == n.k) return;
  43. 		for(int i =0; i < 2; i++) {
  44. 			if(i == 0) n.k =(n.z+n.k)/2;
  45. 			else {n.z =n.k; n.k =T[akt].k;}
  46. 			T[akt].son[i] =T.size();
  47. 			T.push_back(n);
  48. 			constI(T[akt].son[i]);}
  49. 		}
  50.  
  51. 	intervalac(int N) {
  52. 		node n;
  53. 		n.z =n.pok =0;
  54. 		n.k =N;
  55. 		n.son[0] =n.son[1] =-1;
  56. 		T.dibs(2*N);
  57. 		T.push_back(n);
  58. 		constI(0);}
  59.  
  60. 	void getF(int akt) {
  61. 		node n =T[akt];
  62. 		if(T[akt].pok == 0) {
  63. 			if(n.son[0] == -1) T[akt].free =1;
  64. 			else T[akt].free =T[n.son[0]].free+T[n.son[1]].free;}
  65. 		else T[akt].free =0;}
  66.  
  67. 	void put(int akt, int zac, int kon, int val) {
  68. 		node n =T[akt];
  69. 		if(n.z >= kon || zac >= n.k) {
  70. 			getF(akt);
  71. 			return;}
  72. 		if(n.z == zac && n.k == kon) {
  73. 			T[akt].pok +=val;
  74. 			getF(akt);
  75. 			return;}
  76.  
  77. 		T[n.son[0]].pok +=n.pok;
  78. 		put(n.son[0],zac,min(kon,(n.z+n.k)/2),val);
  79. 		T[n.son[1]].pok +=n.pok;
  80. 		put(n.son[1],max(zac,(n.z+n.k)/2),kon,val);
  81. 		T[akt].pok =0;
  82.  
  83. 		int m =OVER9000;
  84. 		for(int i =0; i < 2; i++) if(n.son[i] != -1)
  85. 			m =min(m,T[n.son[i]].pok);
  86. 		if(m == OVER9000) m =0;
  87. 		for(int i =0; i < 2; i++) if(n.son[i] != -1) {
  88. 			T[n.son[i]].pok -=m;
  89. 			getF(n.son[i]);}
  90. 		T[akt].pok +=m;
  91. 		getF(akt);}
  92. };
  93.  
  94. int main() {
  95. 	cin.sync_with_stdio(0);
  96. 	cin.tie(0);
  97. 	int N,M,D,L;
  98. 	cin >> N >> M >> D >> L;
  99. 	intervalac I(N);
  100.  
  101. 	map<int,int> A;
  102. 	A[0] =0;
  103. 	for(int i =1; i < N; i++) {
  104. 		int a;
  105. 		cin >> a;
  106. 		A[a] =i;}
  107.  
  108. 	map<int, pair<int,int> > P;
  109. 	for(int i =0; i < M; i++) {
  110. 		int a;
  111. 		cin >> a;
  112. 		pair<int,int> p =make_pair(N,N);
  113. 		auto it =A.lower_bound(a-L);
  114. 		if(it != A.end()) p.ff =it->ss;
  115. 		it =A.upper_bound(a+L);
  116. 		if(it != A.end()) p.ss =it->ss;
  117. 		P[a] =p;
  118. 		I.put(0,p.ff,p.ss,1);}
  119.  
  120. 	cout << N-I.T[0].free << "\n";
  121. 	for(int i =0; i < D; i++) {
  122. 		int a,b;
  123. 		cin >> a >> b;
  124. 		auto it =P.find(a);
  125. 		pair<int,int> p =it->ss;
  126. 		P.erase(it);
  127. 		I.put(0,p.ff,p.ss,-1);
  128.  
  129. 		auto jt =A.lower_bound(b-L);
  130. 		if(jt != A.end()) p.ff =jt->ss;
  131. 		else p.ff =N;
  132. 		jt =A.upper_bound(b+L);
  133. 		if(jt != A.end()) p.ss =jt->ss;
  134. 		else p.ss =N;
  135. 		P[b] =p;
  136. 		I.put(0,p.ff,p.ss,1);
  137.  
  138. 		cout << N-I.T[0].free << "\n";}
  139. 	return 0;}
  140.  
  141. // look at my code
  142. // my code is amazing
Runtime error #stdin #stdout 0.02s 17816KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/qRPy4I
CT S02E07 E
language:
C++14 (gcc 8.3)
created:
10 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!