이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 |
---|
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... |