-
Notifications
You must be signed in to change notification settings - Fork 2
/
10107.cpp
120 lines (108 loc) · 1.66 KB
/
10107.cpp
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
#include<stdio.h>
#define MAXN 10000
int A[MAXN], B[MAXN];
int inda, indb;
int Largest(int i, int n) {
int l, r, largest;
l = i*2;
r = l+1;
if(l<=n && A[l] > A[i])
largest = l;
else
largest = i;
if(r<= n && A[r] > A[largest])
largest = r;
return largest;
}
int Smallest(int i, int n) {
int l, r, smallest;
l = i*2;
r = l+1;
if(l<=n && B[l] < B[i])
smallest = l;
else
smallest = i;
if(r<= n && B[r] < B[smallest])
smallest = r;
return smallest;
}
void MAX_HEAP(int n, int i) {
int larg, temp;
larg = Largest(i, n);
while(larg != i) {
temp = A[i];
A[i] = A[larg];
A[larg] = temp;
i = larg;
larg = Largest(i,n);
}
}
void MIN_HEAP(int n, int i) {
int Small, temp;
Small = Smallest(i, n);
while(Small != i) {
temp = B[i];
B[i] = B[Small];
B[Small] = temp;
i = Small;
Small = Smallest(i,n);
}
}
void InsertA(int key, int i) {
int par = i/2, temp;
A[i] = key;
while(i>1 && A[par]<A[i]) {
temp = A[par];
A[par] = A[i];
A[i] = temp;
i = par;
par = i/2;
}
}
void InsertB(int key, int i) {
int par = i/2, temp;
B[i] = key;
while(i>1 && B[par]>B[i]) {
temp = B[par];
B[par] = B[i];
B[i] = temp;
i = par;
par = i/2;
}
}
void Cal(int n) {
//long
long long p;
if(inda == indb) {
if(A[1]>n) {
InsertB(A[1],indb+1);
A[1] = n;
MAX_HEAP(inda,1);
}
else
InsertB(n,indb+1);
indb++;
}
else {
if(B[1]<n) {
InsertA(B[1],inda+1);
B[1] = n;
MIN_HEAP(indb,1);
}
else
InsertA(n,inda+1);
inda++;
}
p = A[1] + B[1];
if(inda != indb) printf("%d\n",B[1]);
else
printf("%lld\n",p/2);
}
int main() {
int n;
inda = indb = 0;
while(scanf("%d",&n) == 1) {
Cal(n);
}
return 0;
}