fork download
copy 
  1. #include <ctime>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <iostream>
  5. #include <algorithm>
  6. using namespace std;
  7.  
  8. typedef long long LL;
  9.  
  10. inline int read()
  11. {
  12. 	int x = 0; int v = 1, c;
  13. 	while(c = getchar(), c < '0' || c > '9') if(c == '-') v = -1;
  14. 	for(; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - '0';
  15. 	return x * v;
  16. }
  17.  
  18. template<typename T> inline void write(T x, int ch = 10)
  19. {
  20. 	static int s[20]; int t = 0;
  21. 	if(x < 0) x = -x, putchar('-');
  22. 	if(x == 0) putchar('0');
  23. 	for(s[t++] = ch; x; x /= 10)
  24. 		s[t++] = x % 10 + '0';
  25. 	while(t--) putchar(s[t]);
  26. }
  27.  
  28. const int maxn = 200005;
  29.  
  30. struct Node *null;
  31. struct Node
  32. {
  33. 	Node *fa, *c[2];
  34. 	int val, sz;
  35.  
  36. 	inline void init(int vv = 0) {
  37. 		fa = c[0] = c[1] = null; sz = 0; val = vv;
  38. 	}
  39.  
  40. 	inline bool ch() {
  41. 		return fa->c[1] == this;
  42. 	}
  43.  
  44. 	inline void maintain() {
  45. 		sz = c[0]->sz + c[1]->sz + 1;
  46. 	}
  47.  
  48. 	inline void setc(Node *o, bool kind) {
  49. 		o->fa = this; c[kind] = o;
  50. 	}
  51.  
  52. 	inline void rotate(Node *&rt) {
  53. 		Node *x = fa, *y = x->fa; int d = ch();
  54. 		if(x == rt) fa = y, rt = this; else y->setc(this, x->ch());
  55. 		x->setc(c[d^1], d); setc(x, d^1);
  56. 		x->maintain(); maintain();
  57. 	}
  58.  
  59. 	inline void splay(Node *&rt) {
  60. 		for(; this != rt; rotate(rt)) {
  61. 			if(fa == rt) continue;
  62. 			if(ch() ^ fa->ch()) rotate(rt);
  63. 			else fa->rotate(rt);
  64. 		}
  65. 	}
  66.  
  67. 	inline Node* find(int pos) {
  68. 		Node *x = this;
  69. 		while(x != null && pos) {
  70. 			int s = x->c[0]->sz + 1;
  71. 			if(pos == s) return x;
  72. 			else if(pos < s) x = x->c[0];
  73. 			else pos -= s, x = x->c[1];
  74. 		}
  75. 		return NULL;
  76. 	}
  77.  
  78. 	void dfs() {
  79. 		if(c[0] != null) c[0]->dfs();
  80. 		if(val != -1) write(val, ' ');
  81. 		if(c[1] != null) c[1]->dfs();
  82. 	}
  83. }nodes[maxn], *root;
  84.  
  85. int n, cur;
  86.  
  87. inline Node* addnode(int val)
  88. {
  89. 	Node *x = nodes + (++cur);
  90. 	x->init(val);
  91. 	x->sz = 1;
  92. 	return x;
  93. }
  94.  
  95. void init()
  96. {
  97. 	// clear the splay
  98. 	cur = 0;
  99. 	null = nodes;
  100. 	null->init();
  101. 	root = addnode(-1);
  102. 	root->setc(addnode(-1), 1);
  103. 	root->maintain();
  104. }
  105.  
  106. void work()
  107. {
  108. 	for(int i = 1; i <= n; ++i)
  109. 	{
  110. 		int pos = read();
  111. 		Node *x = root->find(pos + 1);
  112. 		Node *y = root->find(pos + 2);
  113. 		x->splay(root);
  114. 		y->splay(x->c[1]);
  115. 		y->setc(addnode(read()), 0);
  116. 		y->maintain(), x->maintain();
  117. 	}
  118. 	root->dfs(); puts("");
  119. }
  120.  
  121. int main()
  122. {
  123. #ifndef ONLINE_JUDGE
  124. 	freopen("input.txt", "r", stdin);
  125. 	freopen("output.txt", "w", stdout);
  126. #endif
  127.  
  128. 	while(scanf("%d", &n) == 1) {
  129. 		init();
  130. 		work();
  131. 	}
  132.  
  133. #ifndef ONLINE_JUDGE
  134. 	fclose(stdin), fclose(stdout);
  135. 	printf("Run Time: %.3fs\n", (double)clock() / CLOCKS_PER_SEC);
  136. #endif
  137. 	return 0;
  138. }
Success #stdin #stdout 0s 7316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/r1JBX9
poj2828平衡树版
language:
C++14 (clang 8.0)
created:
9 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!