| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 637389 | MohamedFaresNebili | 팀들 (IOI15_teams) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "teams.h"
using namespace std;
using ll = long long;
const int INF = INT32_MAX;
ll N, C[500005], A[500005], B[500005];
vector<ll> P[500005];
struct node {
ll val;
node *l, *r;
node() {
l = nullptr, r = nullptr; val = 0;
}
node(ll x) : val(x), l(nullptr), r(nullptr) {}
node(node *ll, node *rr) {
l = ll, r = rr;
val = 0;
if (l) val += l->val;
if (r) val += r->val;
}
node(node *cp) : val(cp->val), l(cp->l), r(cp->r) {}
};
node* ST[500005];
node* update(node* v, ll l, ll r, ll pos, ll x) {
if (l == r) return new node(v->val + x);
ll mid = (l + r) / 2;
if (pos > mid) {
if(!v->r) v->r = new node();
return new node(v->l, update(v->r, mid + 1, r, pos, x));
}
else {
if(!v->l) v->l = new node();
return new node(update(v->l, l, mid, pos, x), v->r);
}
}
node* emp;
ll query(node* v, node* v0, ll l, ll r, ll lo, ll hi) {
if (l > hi || r < lo) return 0;
if (l >= lo && r <= hi) return v->val - v0->val;
ll md = (l + r) / 2;
ll a = 0, b = 0;
if(v -> l) {
if(v0 -> l) a = query(v -> l, v0 -> l, l, md, lo, hi);
else a = query(v -> l, emp, l, md, lo, hi);
}
if(v -> r) {
if(v0 -> r) b = query(v -> r, v0 -> r, md + 1, r, lo, hi);
else b = query(v -> r, emp, md + 1, r, lo, hi);
}
return a + b;
}
ll query(node* root, node* root0, ll lo, ll hi) { return query(root, root0, 1, N, lo, hi); }
void init(int n, int a[], int b[]) {
N = n; ST[0] = new node(); emp = new node();
for(ll l = 0; l < N; l++)
A[l] = a[l], B[l] = b[l];
for(ll l = 0; l < N; l++)
P[A[l]].push_back(B[l]);
for(ll l = 1; l <= N; l++) {
ST[l] = new node(ST[l - 1]);
for(auto u : P[l])
ST[l] = update(ST[l], 1, N, u, 1);
}
}
ll can(int M, int K[]) {
ll S = 0;
for(ll l = 0; l < M; l++) S += K[l];
if(S > N) return 0;
vector<ll> V;
for(ll l = 0; l < M; l++)
V.push_back(K[l]), C[K[l]]++;
sort(V.begin(), V.begin());
V.erase(unique(V.begin(), V.end()), V.end());
vector<ll> rem(V.size(), 0);
for(ll i = 0; i < V.size(); i++) {
ll U = V[i];
ll cur = U * C[U];
for(ll j = i; j < V.size(); j++) {
ll hi = (j == V.size() - 1 ? N : V[j + 1] - 1);
ll calc = min(cur, query(ST[U], ST[0], V[j], hi) - rem[j]);
cur -= calc; rem[j] += calc;
if(cur == 0) break;
}
if(cur > 0) {
for(auto u : V) C[u] = 0;
return 0;
}
}
for(auto u : V) C[u] = 0;
return 1;
}