fork download
copy 
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <cstring>
  4. #include <cmath>
  5. #include <algorithm>
  6. #include <fstream>
  7. #include<stdlib.h>
  8.  
  9. #define rep( i, l, r ) for (int i = l; i <= r; i++)
  10. #define down( i, l, r ) for (int i = l; i >= r; i--)
  11.  
  12. using namespace std;
  13.  
  14. const int DS = 80000;
  15. const int MaxNum = 2147483647;
  16.  
  17. int o, now, h[DS], l[DS], r[DS], n[DS], last, a, m, ans, num[DS];
  18.  
  19. int NewTree()
  20. {
  21. 	int w = last; last = n[w];
  22. 	n[w] = h[w] = l[w] = r[w] = num[w] = 0;
  23. 	return w;
  24. }
  25.  
  26. void LRotato(int w)
  27. {
  28. 	int o = h[w];
  29. 	if (l[h[o]] == o) l[h[o]] = w; else r[h[o]] = w; h[w] = h[o];
  30. 	r[o] = l[w]; h[l[w]] = o;
  31. 	h[o] = w; l[w] = o;
  32. }
  33.  
  34. void RRotato(int w)
  35. {
  36. 	int o = h[w];
  37. 	if (l[h[o]] == o) l[h[o]] = w; else r[h[o]] = w; h[w] = h[o];
  38. 	l[o] = r[w]; h[r[w]] = o;
  39. 	h[o] = w; r[w] = o;
  40. }
  41.  
  42. void Splay(int w)
  43. {
  44. 	if (w == 0) return;
  45. 	while (h[w] != 0)
  46. 	{
  47. 		if (l[h[w]] == w) RRotato(w); else LRotato(w);
  48. 	}
  49. }
  50.  
  51. int Pre()
  52. {
  53. 	int p = l[l[0]];
  54. 	if (p == 0) return 0;
  55. 	while (r[p] != 0) p = r[p];
  56. 	return p;
  57. }
  58.  
  59. int Suf()
  60. {
  61. 	int p = r[l[0]];
  62. 	if (p == 0) return 0;
  63. 	while (l[p] != 0) p = l[p];
  64. 	return p;
  65. }
  66.  
  67. void Insert(int m)
  68. {
  69. 	now++;
  70. 	int p = l[0], c = 0, w = 0; 
  71. 	bool b = true;
  72. 	while (p != 0)
  73. 	{
  74. 		if (m <= num[p])
  75. 		{
  76. 			c = p; p = l[p]; b = true;
  77. 		}
  78. 		else
  79. 		{
  80. 			c = p; p = r[p]; b = false;
  81. 		}
  82. 	}
  83. 	w = NewTree();
  84. 	h[w] = c; if (b) l[c] = w; else r[c] = w; num[w] = m;
  85. 	Splay(w);
  86. }
  87.  
  88. void Delete(int w)
  89. {
  90. 	now--;
  91. 	int o = h[w];
  92. 	if (l[o] == w) l[o] = 0; else r[o] = 0;
  93. 	n[w] = last; last = w;
  94. }
  95.  
  96. int FindAim(int m)
  97. {
  98. 	int w = last;
  99. 	Insert(m);
  100. 	int a = Pre(), b = Suf(), aa = 0, bb = 0;
  101. 	if (a != 0) aa = m - num[a]; else aa = MaxNum;
  102. 	if (b != 0) bb = num[b] - m; else bb = MaxNum;
  103. 	if (aa <= bb) 
  104. 	{
  105. 		Splay(a); Splay(b); Delete(w); 
  106. 		w = a; Splay(w); a = Pre(); b = Suf(); 
  107. 		Splay(a); Splay(b); Delete(w); 
  108. 		return aa;
  109. 	}
  110. 	else
  111. 	{
  112. 		Splay(a); Splay(b); Delete(w); 
  113. 		w = b; Splay(w); a = Pre(); b = Suf(); 
  114. 		Splay(a); Splay(b); Delete(w); 
  115. 		return bb;
  116. 	}
  117. }
  118.  
  119. int main()
  120. {
  121. 	ans = now = 0; 
  122. 	bool b = false; 
  123. 	rep(i, 1, DS-1) n[i] = i+1; last = 1; 
  124. 	scanf("%d", &o);
  125. 	rep(i, 1, o)
  126. 	{
  127. 		scanf("%d%d", &a, &m);
  128. 		if (now == 0) 
  129. 		{
  130. 			Insert(m);
  131. 			if (a == 0) b = true; else b = false;
  132. 		}
  133. 		else
  134. 		{
  135. 			if (b == (a == 0)) Insert(m); else ans += FindAim(m) % 1000000;
  136. 		}
  137. 		ans = ans % 1000000;
  138. 	}
  139. 	printf("%d", ans);
  140. 	return 0;
  141. }
  142.  
Success #stdin #stdout 0s 4908KB
comments (?)
stdin
copy 
5
0 2
0 4
1 3
1 2
1 5
stdout
copy 
3
https://ideone.com/XkpKul
BZOJ 1208
language:
C++ (gcc 8.3)
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!