# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
429165 |
2021-06-15T18:01:30 Z |
timmyfeng |
Teams (IOI15_teams) |
C++17 |
|
1459 ms |
207264 KB |
#include <bits/stdc++.h>
using namespace std;
const int N = 500001, S = 64 * N;
int sum[S], child[S][2], ptr = 1;
int segtree(int x) {
child[ptr][0] = child[ptr][1] = 0;
sum[ptr] = x;
return ptr++;
}
int segtree(int l, int r) {
child[ptr][0] = l, child[ptr][1] = r;
sum[ptr] = sum[l] + sum[r];
return ptr++;
}
int build(int l, int r) {
int u = segtree(0);
if (l < r) {
int m = (l + r) / 2;
child[u][0] = build(l, m);
child[u][1] = build(m + 1, r);
}
return u;
}
int update(int u, int a, int x, int l, int r) {
if (l == r) {
return segtree(sum[u] + x);
} else {
int m = (l + r) / 2;
if (a <= m) {
return segtree(update(child[u][0], a, x, l, m), child[u][1]);
} else {
return segtree(child[u][0], update(child[u][1], a, x, m + 1, r));
}
}
}
int copy(int u, int v, int a, int b, int l, int r) {
if (b < a || b < l || r < a) {
return v;
} else if (a <= l && r <= b) {
return u;
} else {
int m = (l + r) / 2;
return segtree(
copy(child[u][0], child[v][0], a, b, l, m),
copy(child[u][1], child[v][1], a, b, m + 1, r)
);
}
}
int assign(int u, int v, int &k) {
if (child[v][0] == 0) {
int delta = min(k, sum[u] - sum[v]);
k -= delta;
return segtree(sum[v] + delta);
} else if (sum[u] - sum[v] <= k) {
k -= sum[u] - sum[v];
return u;
} else {
int l = assign(child[u][0], child[v][0], k);
int r = k > 0 ? assign(child[u][1], child[v][1], k) : child[v][1];
return segtree(l, r);
}
}
int root[N], n;
void init(int n, int a[], int b[]) {
::n = n;
vector<array<int, 2>> students;
for (int i = 0; i < n; ++i) {
students.push_back({a[i], b[i]});
}
sort(students.begin(), students.end());
root[0] = build(1, n);
for (int i = 1, j = 0; i <= n; ++i) {
root[i] = root[i - 1];
while (j < n && students[j][0] == i) {
root[i] = update(root[i], students[j++][1], 1, 1, n);
}
}
}
bool can(int m, int k[]) {
int temp = ptr;
sort(k, k + m);
int used = root[0];
for (int i = 0; i < m; ++i) {
used = copy(root[k[i]], used, 1, k[i] - 1, 1, n);
used = assign(root[k[i]], used, k[i]);
if (k[i] > 0) {
return false;
}
}
ptr = temp;
return true;
}
Compilation message
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:74:15: warning: declaration of 'n' shadows a global declaration [-Wshadow]
74 | void init(int n, int a[], int b[]) {
| ~~~~^
teams.cpp:72:14: note: shadowed declaration is here
72 | int root[N], n;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
304 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
300 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
304 KB |
Output is correct |
8 |
Correct |
1 ms |
296 KB |
Output is correct |
9 |
Correct |
1 ms |
300 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
22 |
Correct |
1 ms |
300 KB |
Output is correct |
23 |
Correct |
1 ms |
332 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
332 KB |
Output is correct |
26 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
76 ms |
26644 KB |
Output is correct |
2 |
Correct |
79 ms |
26680 KB |
Output is correct |
3 |
Correct |
74 ms |
26636 KB |
Output is correct |
4 |
Correct |
73 ms |
26772 KB |
Output is correct |
5 |
Correct |
48 ms |
26204 KB |
Output is correct |
6 |
Correct |
38 ms |
26208 KB |
Output is correct |
7 |
Correct |
40 ms |
26204 KB |
Output is correct |
8 |
Correct |
40 ms |
26232 KB |
Output is correct |
9 |
Correct |
58 ms |
37704 KB |
Output is correct |
10 |
Correct |
49 ms |
31184 KB |
Output is correct |
11 |
Correct |
37 ms |
26504 KB |
Output is correct |
12 |
Correct |
36 ms |
25356 KB |
Output is correct |
13 |
Correct |
68 ms |
26764 KB |
Output is correct |
14 |
Correct |
45 ms |
25864 KB |
Output is correct |
15 |
Correct |
61 ms |
26552 KB |
Output is correct |
16 |
Correct |
67 ms |
26680 KB |
Output is correct |
17 |
Correct |
44 ms |
26824 KB |
Output is correct |
18 |
Correct |
43 ms |
26936 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
75 ms |
26876 KB |
Output is correct |
2 |
Correct |
82 ms |
26820 KB |
Output is correct |
3 |
Correct |
265 ms |
38576 KB |
Output is correct |
4 |
Correct |
77 ms |
26860 KB |
Output is correct |
5 |
Correct |
74 ms |
26424 KB |
Output is correct |
6 |
Correct |
73 ms |
32176 KB |
Output is correct |
7 |
Correct |
46 ms |
26440 KB |
Output is correct |
8 |
Correct |
67 ms |
30500 KB |
Output is correct |
9 |
Correct |
59 ms |
37584 KB |
Output is correct |
10 |
Correct |
79 ms |
31548 KB |
Output is correct |
11 |
Correct |
82 ms |
27036 KB |
Output is correct |
12 |
Correct |
98 ms |
28420 KB |
Output is correct |
13 |
Correct |
183 ms |
41972 KB |
Output is correct |
14 |
Correct |
321 ms |
41640 KB |
Output is correct |
15 |
Correct |
115 ms |
36760 KB |
Output is correct |
16 |
Correct |
106 ms |
36772 KB |
Output is correct |
17 |
Correct |
83 ms |
35320 KB |
Output is correct |
18 |
Correct |
87 ms |
36544 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
617 ms |
139992 KB |
Output is correct |
2 |
Correct |
648 ms |
140668 KB |
Output is correct |
3 |
Correct |
1308 ms |
171044 KB |
Output is correct |
4 |
Correct |
611 ms |
145884 KB |
Output is correct |
5 |
Correct |
330 ms |
143116 KB |
Output is correct |
6 |
Correct |
297 ms |
153632 KB |
Output is correct |
7 |
Correct |
228 ms |
143148 KB |
Output is correct |
8 |
Correct |
292 ms |
148704 KB |
Output is correct |
9 |
Correct |
340 ms |
207264 KB |
Output is correct |
10 |
Correct |
305 ms |
147864 KB |
Output is correct |
11 |
Correct |
342 ms |
142556 KB |
Output is correct |
12 |
Correct |
442 ms |
147772 KB |
Output is correct |
13 |
Correct |
828 ms |
176892 KB |
Output is correct |
14 |
Correct |
1459 ms |
177592 KB |
Output is correct |
15 |
Correct |
617 ms |
165928 KB |
Output is correct |
16 |
Correct |
585 ms |
164208 KB |
Output is correct |
17 |
Correct |
340 ms |
163484 KB |
Output is correct |
18 |
Correct |
337 ms |
163156 KB |
Output is correct |