# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
396741 |
2021-04-30T17:02:46 Z |
WLZ |
Teams (IOI15_teams) |
C++14 |
|
3749 ms |
524292 KB |
#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
struct node {
int l, r, val;
node *left, *right;
};
node *build(int l, int r) {
if (l == r) return new node{l, r, 0, nullptr, nullptr};
node *left = build(l, (l + r) / 2), *right = build((l + r) / 2 + 1, r);
return new node{l, r, 0, left, right};
}
node *update(node *cur, int x, int val) {
if (cur->l == cur->r) return new node{cur->l, cur->r, cur->val + val, nullptr, nullptr};
if (x <= cur->left->r) {
node *left = update(cur->left, x, val);
return new node{cur->l, cur->r, left->val + cur->right->val, left, cur->right};
} else {
node *right = update(cur->right, x, val);
return new node{cur->l, cur->r, cur->left->val + right->val, cur->left, right};
}
}
int query(node *cur, int l, int r) {
if (l > r) return 0;
if (cur->l > r || cur->r < l) return 0;
if (l <= cur->l && cur->r <= r) return cur->val;
return query(cur->left, l, r) + query(cur->right, l, r);
}
int n;
vector<node*> root;
void init(int N, int A[], int B[]) {
n = N;
vector< pair<int, int> > v(n);
for (int i = 0; i < n; i++) v[i].first = A[i], v[i].second = B[i];
sort(v.begin(), v.end());
root.resize(n + 1); root[0] = build(1, n);
for (int i = 1, j = 0; i <= n; i++) {
root[i] = root[i - 1];
while (j < N && v[j].first == i) root[i] = update(root[i], v[j++].second, +1);
}
}
int can(int M, int K[]) {
if (accumulate(K, K + M, 0ll) > n) return 0;
sort(K, K + M);
vector<int> used(M, 0);
for (int i = 0; i < M; i++) {
int left = K[i], ptr = i;
while (ptr < M) {
int cnt = query(root[K[i]], K[ptr], ptr < M - 1 ? K[ptr + 1] - 1 : n) - used[ptr];
used[ptr] += min(cnt, left);
left -= min(cnt, left);
if (left <= 0) break;
ptr++;
}
if (ptr == M && left > 0) return 0;
}
return 1;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 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 |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
296 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
2 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
292 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 |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
204 KB |
Output is correct |
21 |
Correct |
1 ms |
204 KB |
Output is correct |
22 |
Correct |
1 ms |
296 KB |
Output is correct |
23 |
Correct |
1 ms |
204 KB |
Output is correct |
24 |
Correct |
1 ms |
224 KB |
Output is correct |
25 |
Correct |
1 ms |
204 KB |
Output is correct |
26 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
179 ms |
96260 KB |
Output is correct |
2 |
Correct |
183 ms |
96156 KB |
Output is correct |
3 |
Correct |
178 ms |
96192 KB |
Output is correct |
4 |
Correct |
190 ms |
96536 KB |
Output is correct |
5 |
Correct |
125 ms |
95836 KB |
Output is correct |
6 |
Correct |
107 ms |
95828 KB |
Output is correct |
7 |
Correct |
114 ms |
95800 KB |
Output is correct |
8 |
Correct |
112 ms |
95884 KB |
Output is correct |
9 |
Correct |
2516 ms |
92668 KB |
Output is correct |
10 |
Correct |
805 ms |
92356 KB |
Output is correct |
11 |
Correct |
117 ms |
97144 KB |
Output is correct |
12 |
Correct |
100 ms |
92500 KB |
Output is correct |
13 |
Correct |
116 ms |
97300 KB |
Output is correct |
14 |
Correct |
114 ms |
93908 KB |
Output is correct |
15 |
Correct |
186 ms |
96184 KB |
Output is correct |
16 |
Correct |
194 ms |
96248 KB |
Output is correct |
17 |
Correct |
130 ms |
97456 KB |
Output is correct |
18 |
Correct |
110 ms |
97668 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
224 ms |
96440 KB |
Output is correct |
2 |
Correct |
234 ms |
96432 KB |
Output is correct |
3 |
Correct |
318 ms |
99540 KB |
Output is correct |
4 |
Correct |
182 ms |
96540 KB |
Output is correct |
5 |
Correct |
129 ms |
96056 KB |
Output is correct |
6 |
Correct |
129 ms |
96120 KB |
Output is correct |
7 |
Correct |
127 ms |
96016 KB |
Output is correct |
8 |
Correct |
127 ms |
96024 KB |
Output is correct |
9 |
Correct |
2404 ms |
92716 KB |
Output is correct |
10 |
Correct |
3749 ms |
92484 KB |
Output is correct |
11 |
Correct |
1118 ms |
97248 KB |
Output is correct |
12 |
Correct |
1435 ms |
92740 KB |
Output is correct |
13 |
Correct |
385 ms |
97476 KB |
Output is correct |
14 |
Correct |
346 ms |
97692 KB |
Output is correct |
15 |
Correct |
203 ms |
96316 KB |
Output is correct |
16 |
Correct |
198 ms |
96316 KB |
Output is correct |
17 |
Correct |
143 ms |
97720 KB |
Output is correct |
18 |
Correct |
143 ms |
97752 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1235 ms |
524292 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |