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 2345678
  12. #define MAX 1037471823
  13. #define Q 1
  14.  
  15. using namespace std;
  16.  
  17. int m, n, a, b, s[MS], l[MS], r[MS], h[MS], next[MS], last, now;
  18. char c[MS], q[10];
  19.  
  20. void Cal(int o) { s[o] = s[l[o]] + s[r[o]] + 1; }
  21.  
  22. int New() { int o = last; last = next[last], s[o] = 1, l[o] = r[o] = h[o] = c[o] = 0; return o; }
  23.  
  24. void Splay(int x)
  25. {
  26. 	if (!x) return; int o = h[x];
  27. 	while (o)
  28. 	{
  29. 		if (l[o] == x) { l[h[o]] == o?l[h[o]] = x: r[h[o]] = x; h[x] = h[o]; l[o] = r[x]; h[r[x]] = o; h[o] = x; r[x] = o; Cal(o); }
  30. 		else { l[h[o]] == o?l[h[o]] = x: r[h[o]] = x; h[x] = h[o]; r[o] = l[x]; h[l[x]] = o; h[o] = x; l[x] = o; Cal(o); }
  31. 		o = h[x];
  32. 	}
  33. 	Cal(x);
  34. }
  35.  
  36. int FindRW(int rr)
  37. {
  38. 	int o = l[0];
  39. 	while (rr != s[l[o]]) if (rr < s[l[o]]) o = l[o]; else rr -= s[l[o]] + 1, o = r[o];
  40. 	return o;
  41. }
  42.  
  43. void InsertP(int o, int n)
  44. {
  45. 	int ln = (n-1)/2, rn = n-1-ln;
  46. 	if (ln) { int now = New(); h[now] = o, l[o] = now; InsertP(now, ln); }
  47. 	c[o] = 0; 
  48. 	while (c[o] < 32 || 126 < c[o]) 
  49. 		scanf("%c", &c[o]);
  50. 	if (rn) { int now = New(); h[now] = o, r[o] = now; InsertP(now, rn); }
  51. 	Cal(o);
  52. }
  53.  
  54. void Insert(int b, int n) { Splay(FindRW(b)); Splay(FindRW(b+1)); int now = New(); h[now] = l[l[0]]; r[l[l[0]]] = now; InsertP(now, n); Cal(l[l[0]]); Cal(l[0]); }
  55.  
  56. void DeleteP(int o) { if (l[o]) DeleteP(l[o]); if (r[o]) DeleteP(r[o]); next[o] = last, last = o; }
  57.  
  58. void Delete(int b, int n) { Splay(FindRW(b-1)); Splay(FindRW(b+n)); DeleteP(r[l[l[0]]]); r[l[l[0]]] = 0; Cal(l[l[0]]); Cal(l[0]); }
  59.  
  60. void PrintP(int o) { if (l[o]) PrintP(l[o]); printf("%c", c[o]); if (r[o]) PrintP(r[o]); }
  61.  
  62. void Print(int b, int n) { Splay(FindRW(b-1)); Splay(FindRW(b+n)); PrintP(r[l[l[0]]]); printf("\n"); }
  63.  
  64. int main()
  65. {
  66. 	scanf("%d", &m); now = 0; l[0] = 1, l[1] = 2, h[2] = 1; s[1] = 2, s[2] = 1;
  67. 	rep(i, 3, MS-1) next[i] = i+1; last = 3;
  68. 	rep(i, 1, m)
  69. 	{
  70. 		scanf("%s", q);
  71. 		if (q[0] == 'M') { scanf("%d", &now); }
  72. 		else if (q[0] == 'I') { scanf("%d", &n); Insert(now, n); }
  73. 		else if (q[0] == 'D') { scanf("%d", &n); if (n > s[l[0]]-2-now) Delete(now+1, s[l[0]]-2-now); else Delete(now+1, n); }
  74. 		else if (q[0] == 'G') { scanf("%d", &n); Print(now+1, n); }
  75. 		else if (q[0] == 'P') now--;
  76. 		else now++;
  77. 	}
  78. 	return 0;
  79. }
Success #stdin #stdout 0s 51456KB
comments (?)
stdin
copy 
15
Insert 26
abcdefghijklmnop
qrstuv wxy
Move 16
Delete 11
Move 5
Insert 1
^
Next
Insert 1
_
Next
Next
Insert 4
.\/.
Get 4
Prev
Insert 1
^
Move 0
Get 22
stdout
copy 
.\/.
abcde^_^f.\/.ghijklmno
https://ideone.com/84Uz7m
BZOJ 1507
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!