This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int N = 500001;
struct segtree {
segtree *left = nullptr, *right = nullptr;
int sum = 0;
segtree() {}
segtree(int l, int r) {
if (l < r) {
int m = (l + r) / 2;
left = new segtree(l, m);
right = new segtree(m + 1, r);
}
}
void pull() {
sum = left->sum + right->sum;
}
segtree * update(int a, int x, int l, int r) {
segtree *res = new segtree();
if (l == r) {
res->sum = sum + x;
} else {
int m = (l + r) / 2;
if (a <= m) {
res->left = left->update(a, x, l, m);
res->right = right;
} else {
res->left = left;
res->right = right->update(a, x, m + 1, r);
}
res->pull();
}
return res;
}
};
segtree * copy(segtree *u, segtree *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;
segtree *res = new segtree();
res->left = copy(u->left, v->left, a, b, l, m);
res->right = copy(u->right, v->right, a, b, m + 1, r);
res->pull();
return res;
}
}
segtree * assign(segtree *u, segtree *v, int &k) {
segtree *res = new segtree();
if (!v->left) {
int delta = min(k, u->sum - v->sum);
res->sum = v->sum + delta;
k -= delta;
return res;
} else if (u->sum - v->sum <= k) {
k -= u->sum - v->sum;
return u;
} else {
res->left = assign(u->left, v->left, k);
res->right = k > 0 ? assign(u->right, v->right, k) : v->right;
res->pull();
return res;
}
}
segtree *root[N];
int 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] = new segtree(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] = root[i]->update(students[j++][1], 1, 1, n);
}
}
}
bool can(int m, int k[]) {
sort(k, k + m);
segtree *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;
}
}
return true;
}
Compilation message (stderr)
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:79:15: warning: declaration of 'n' shadows a global declaration [-Wshadow]
79 | void init(int n, int a[], int b[]) {
| ~~~~^
teams.cpp:77:5: note: shadowed declaration is here
77 | int n;
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |