1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
| /**************************************************************
Problem: 1588
User: abcdabcd987
Language: C++
Result: Accepted
Time:116 ms
Memory:1888 kb
****************************************************************/
#include <iostream>
using namespace std;
struct TreeNode;
typedef TreeNode* Node;
struct TreeNode
{
int x;
Node Parent, LeftChild, RightChild;
TreeNode(const int _x = 0, const Node _P = NULL, const Node _L = NULL, const Node _R = NULL):
x(_x), Parent(_P), LeftChild(_L), RightChild(_R) { }
} h[40000];
int _top, n, x, MinDelta, sum;
Node root;
void Zag(Node x)
{
Node y = x->Parent;
y->RightChild = x->LeftChild;
if (x->LeftChild)
x->LeftChild->Parent = y;
x->Parent = y->Parent;
if (y->Parent)
if (y == y->Parent->LeftChild)
y->Parent->LeftChild = x;
else
y->Parent->RightChild = x;
y->Parent = x;
x->LeftChild = y;
}
void Zig(Node x)
{
Node y = x->Parent;
y->LeftChild = x->RightChild;
if (x->RightChild)
x->RightChild->Parent = y;
x->Parent = y->Parent;
if (y->Parent)
if (y == y->Parent->LeftChild)
y->Parent->LeftChild = x;
else
y->Parent->RightChild = x;
y->Parent = x;
x->RightChild = y;
}
void Splay(Node x)
{
while (Node p = x->Parent)
{
if (p->Parent == NULL)
{
if (x == p->LeftChild) Zig(x);
else Zag(x);
break;
}
else
if (x == p->LeftChild)
if (p == p->Parent->LeftChild)
Zig(p), Zig(x);
else
Zig(x), Zag(x);
else
if (p == p->Parent->RightChild)
Zag(p), Zag(x);
else
Zag(x), Zig(x);
}
root = x;
}
Node Insert(const int x)
{
h[++_top] = TreeNode(x);
Node t = root, p;
while (t)
{
p = t;
if (x == t->x)
{
--_top;
Splay(t);
MinDelta = 0;
return t;
}
t = (x < t->x) ? t->LeftChild : t->RightChild;
}
(x <= p->x ? p->LeftChild : p->RightChild) = &h[_top];
h[_top].Parent = p;
Splay(&h[_top]);
return &h[_top];
}
int GetMin(Node t)
{
if (t == NULL) return 0x0FFFFFFF;
Node p;
while (t)
{
p = t;
t = t->LeftChild;
}
return p->x;
}
int GetMax(Node t)
{
if (t == NULL) return 0xA0000000;
Node p;
while (t)
{
p = t;
t = t->RightChild;
}
return p->x;
}
int main()
{
ios::sync_with_stdio(false);
cin >> n >> h[++_top].x;
root = &h[_top];
sum = h[_top].x;
for(int i = 1, x; i < n; ++i)
{
x = 0;
cin >> x;
MinDelta = 0x7FFFFFFF;
Insert(x);
if (MinDelta == 0x7FFFFFFF)
MinDelta = min(x-GetMax(root->LeftChild), GetMin(root->RightChild)-x);
sum += MinDelta;
}
cout << sum;
}
|
