| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1282366 | iamhereforfun | Teams (IOI15_teams) | C++20 | 0 ms | 0 KiB |
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 500000;
class SegmentTree {
private:
vector<int> tree;
int n;
void build_tree(int node, int l, int r, const vector<int>& arr) {
if (l == r) {
tree[node] = arr[l];
return;
}
int mid = (l + r) / 2;
build_tree(2 * node, l, mid, arr);
build_tree(2 * node + 1, mid + 1, r, arr);
tree[node] = min(tree[2 * node], tree[2 * node + 1]);
}
int query_tree(int node, int l, int r, int ql, int qr) {
if (ql > r || qr < l) return 1e9;
if (ql <= l && r <= qr) return tree[node];
int mid = (l + r) / 2;
int left_val = query_tree(2 * node, l, mid, ql, qr);
int right_val = query_tree(2 * node + 1, mid + 1, r, ql, qr);
return min(left_val, right_val);
}
public:
void build(const vector<int>& arr, int l, int r) {
n = r - l + 1;
tree.resize(4 * n);
build_tree(1, l, r, arr);
}
int query(int ql, int qr) {
return query_tree(1, 1, n, ql, qr);
}
};
vector<int> H;
SegmentTree segTree;
void init(int N, int A[], int B[]) {
int n = N;
vector<int> freq(n + 2, 0);
for (int i = 0; i < n; i++) {
int b = B[i];
if (b > n) b = n;
freq[b]++;
}
H.resize(n + 1);
H[n] = freq[n];
for (int x = n - 1; x >= 1; x--) {
H[x] = H[x + 1] + freq[x];
}
segTree.build(H, 1, n);
}
int can(int M, int K[]) {
sort(K.begin(), K.end());
long long total = 0;
for (int k : K) total += k;
vector<long long> SS(M);
for (int i = M - 1; i >= 0; i--) {
SS[i] = total;
total -= K[i];
}
for (int i = 0; i < M; i++) {
int L = (i == 0) ? 1 : K[i - 1] + 1;
int R = K[i];
if (L > R) continue;
int minH = segTree.query(L, R);
if (minH < SS[i]) {
return 0;
}
}
return 1;
}