fork download
copy 
  1. #include <cstring>
  2. #include <cmath>
  3. #include <algorithm>
  4. #include <cstdlib>
  5. #include <cstdio>
  6. #include <fstream>
  7. #include <iostream>
  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. #define MS 123456
  12. #define MAX 1037471823
  13. #define Q 1
  14.  
  15. using namespace std;
  16.  
  17. int n, m, low, a, l[MS], r[MS], h[MS], s[MS], ans, now;
  18. long long k[MS];
  19. char q[5];
  20.  
  21. void Splay(int x)
  22. {
  23. 	if (!x) return; int o = h[x];
  24. 	while (o)
  25. 	{
  26. 		if (l[o] == x) { l[h[o]] == o ? l[h[o]] = x : r[h[o]] = x; h[x] = h[o], h[r[x]] = o, l[o] = r[x], h[o] = x, r[x] = o, s[o] = s[l[o]] + s[r[o]] + 1, s[x] = s[l[x]] + s[r[x]] + 1; } 
  27. 		else { l[h[o]] == o ? l[h[o]] = x : r[h[o]] = x; h[x] = h[o], h[l[x]] = o, r[o] = l[x], h[o] = x, l[x] = o, s[o] = s[l[o]] + s[r[o]] + 1, s[x] = s[l[x]] + s[r[x]] + 1; } 
  28. 		o = h[x];
  29. 	}
  30. }
  31.  
  32. int Pre(int x)
  33. {
  34. 	int o; if (r[x]) for (o = r[x]; l[o]; o = l[o]); else for (o = h[x]; o && l[o] != x; x = o, o = h[x]); return o;
  35. }
  36.  
  37. void Insert(int x)
  38. {
  39. 	if (x < low - m) return;
  40. 	if (l[0] == 0) { now++, s[now] = 1, h[now] = l[now] = r[now] = 0, k[now] = x, l[0] = now; return; }
  41. 	int o; for (o = l[0]; x < k[o]?l[o]:r[o];) s[o]++, o = x < k[o]?l[o]:r[o]; s[o]++;
  42. 	now++; if (x < k[o]) l[o] = now; else r[o] = now; s[now] = 1, h[now] = o, l[now] = r[now] = 0, k[now] = x; Splay(now);
  43. }
  44.  
  45. void Check(double x)
  46. {
  47. 	if (l[0] == 0) return;
  48. 	int o; for (o = l[0]; x < k[o]?l[o]:r[o];) s[o]++, o = x < k[o]?l[o]:r[o]; s[o]++;
  49. 	now++; if (x < k[o]) l[o] = now; else r[o] = now; s[now] = 1, h[now] = o, l[now] = r[now] = 0; 
  50. 	if (Pre(now)) { Splay(Pre(now)); ans += s[l[l[0]]]-1, s[l[0]] -= s[l[l[0]]]; l[l[0]] = 0; } else ans += s[l[0]]-1, l[0] = 0; now--;
  51. }
  52.  
  53. int FindRW(int x)
  54. {
  55. 	if (x >= s[l[0]]) return -1-m; int o = l[0];
  56. 	while (x != s[r[o]]) if (x < s[r[o]]) o = r[o]; else x -= s[r[o]] + 1, o = l[o];
  57. 	return k[o];
  58. }
  59.  
  60. int main()
  61. {
  62. 	scanf("%d%d", &n, &low); ans = m = 0;
  63. 	rep(i, 1, n)
  64. 	{
  65. 		scanf("%s%d", q, &a);
  66. 		if (q[0] == 'I') Insert(a-m);
  67. 		else if (q[0] == 'A') m += a;
  68. 		else if (q[0] == 'S') { m -= a; Check(low-m-0.5); }
  69. 		else if (q[0] == 'F') printf("%d\n", FindRW(a-1)+m);
  70. 	}
  71. 	printf("%d\n", ans);
  72. 	return 0;
  73. }
Success #stdin #stdout 0s 6192KB
comments (?)
stdin
copy 
9 10
I 60
I 70
S 50
F 2
I 30
S 15
A 5
F 1
F 2
stdout
copy 
10
20
-1
2
https://ideone.com/GsGlSV
BZOJ 1503
language:
C++ (gcc 8.3)
created:
10 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!