fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i++)
  4. #define DOW(i,a,b) for (int i=(a),_b=(b);i>=_b;i--)
  5. #define probability 0.5
  6. #define maxlevel 19
  7.  
  8. using namespace std;
  9.  
  10. typedef pair<int,int> PII;
  11. typedef long long LL;
  12. typedef unsigned long long ULL;
  13.  
  14. struct node{
  15. 	node *left, *right, *down;
  16. 	int val, len;
  17. } *head[maxlevel+1], *path[maxlevel+1], *nil;
  18.  
  19. const int oo = 2e9;
  20.  
  21. int curmaxh, listlen;
  22. int indexdist[maxlevel+1];
  23.  
  24. void init(){
  25. 	nil = new node;
  26. 	nil->val = oo;
  27. 	nil->len = 0;
  28.  
  29. 	FOR(i,1,maxlevel){
  30. 		head[i] = new node;
  31. 		if (i != 1)
  32. 			head[i]->down = head[i-1];
  33. 		else head[i]->down = NULL;
  34. 		head[i]->left = nil;
  35. 		head[i]->val = -oo;
  36. 		head[i]->len = 0;
  37. 	}
  38.  
  39. 	FOR(i,1,maxlevel) path[i] = new node;
  40. 	memset(path, 0, sizeof(node*) * (maxlevel+1));
  41. 	curmaxh = 1;
  42. }
  43.  
  44. node *search(int value){
  45. 	node *curpos = head[curmaxh];
  46. 	int curh = curmaxh;
  47. 	indexdist[0] = 0;
  48.  
  49. 	while (1){
  50. 		indexdist[curh] = 0;
  51. 		while (curpos->left->val <= value){
  52. 			indexdist[curh] += curpos->len;
  53. 			curpos = curpos->left;
  54. 		}
  55.  
  56. 		indexdist[0] += indexdist[curh];
  57. 		path[curh] = curpos;
  58. 		curh--;
  59.  
  60. 		if (curpos->down != NULL)
  61. 			curpos = curpos->down;
  62. 		else break;
  63. 	}
  64.  
  65. 	return curpos;
  66. }
  67.  
  68. node *searchindex(int idx){
  69. 	int curidx = idx;
  70. 	node *curpos = head[curmaxh];
  71.  
  72. 	while (true){
  73. 		while (curpos->left != nil && curidx >= curpos->len){
  74. 			curidx -= curpos->len;
  75. 			curpos = curpos->left;
  76. 		}
  77.  
  78. 		if (curpos->down != NULL)
  79. 			curpos = curpos->down;
  80. 		else break;
  81. 	}
  82.  
  83. 	if (curidx > 0) curpos = NULL;
  84. 	return curpos;
  85. }
  86.  
  87. void remove(int value){
  88. 	if (search(value)->val != value) return;
  89. 	listlen--;
  90.  
  91. 	bool curstate = 1;
  92.  
  93. 	FOR(i,1,curmaxh){
  94. 		curstate = curstate && (path[i]->down == path[i-1]);
  95. 		if (curstate){
  96. 			if (path[i]->right != NULL)
  97. 				path[i]->right->left = path[i]->left;
  98. 			if (path[i]->left != NULL)
  99. 				path[i]->left->right = path[i]->right;
  100.  
  101. 			if (path[i]->right != NULL)
  102. 				path[i]->right->len = path[i]->right->len + path[i]->len - 1;
  103. 		}
  104. 		else path[i]->len--;
  105. 	}
  106. }
  107.  
  108. int getlevel(){
  109. 	int level = 1;
  110. 	while ((float)rand() / RAND_MAX < probability && level < maxlevel)
  111. 		level++;
  112. 	return level;
  113. }
  114.  
  115. node *insertnode(node *insertpoint, node *child, int x, int value){
  116. 	node *newnode = new node;
  117. 	newnode->val = value;
  118. 	newnode->len = insertpoint->len - x;
  119. 	newnode->down = child;
  120. 	newnode->left = insertpoint->left;
  121. 	newnode->right = insertpoint;
  122. 	newnode->left->right = newnode;
  123.  
  124. 	insertpoint->len = x + 1;
  125. 	insertpoint->left = newnode;
  126.  
  127. 	return newnode;
  128. }
  129.  
  130. void insert(int value){
  131. 	if (search(value)->val == value) return;
  132. 	listlen++;
  133.  
  134. 	node *curpos = NULL;
  135. 	srand(time(NULL));
  136. 	int newlevel = getlevel();
  137. 	indexdist[0] = 0;
  138. 	FOR(i,1,newlevel){
  139. 		if (i <= curmaxh)
  140. 			curpos = insertnode(path[i], curpos, indexdist[i-1], value);
  141. 		else{
  142. 			head[i]->len = listlen;
  143. 			curpos = insertnode(head[i], curpos, indexdist[i-1], value);
  144. 		}
  145.  
  146. 		indexdist[i] += indexdist[i-1];
  147. 	}
  148.  
  149. 	FOR(i,newlevel+1,curmaxh)
  150. 		path[i]->len++;
  151.  
  152. 	curmaxh = max(curmaxh, newlevel);
  153. }
  154.  
  155. int main(){
  156. 	//freopen("input.inp","r",stdin);
  157. 	//freopen("output.out","w",stdout);
  158. 	init();
  159.  
  160. 	int q;
  161. 	scanf("%d\n",&q);
  162. 	while (q--){
  163. 		char req;   int x;
  164. 		scanf("%c%d\n",&req,&x);
  165.  
  166. 		if (req == 'I') insert(x);
  167. 		if (req == 'D') remove(x);
  168. 		if (req == 'K'){
  169. 			node *tmp = searchindex(x);
  170. 			if (tmp == NULL)
  171. 				printf("invalid\n");
  172. 			else printf("%d\n",tmp->val);
  173. 		}
  174. 		if (req == 'C'){
  175. 			search(x-1);
  176. 			printf("%d\n",indexdist[0]);
  177. 		}
  178. 	}
  179. 	return 0;
  180. }
Time limit exceeded #stdin #stdout 5s 3464KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/8RHICk
language:
C++ (gcc 8.3)
created:
7 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!