| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 637405 | MohamedFaresNebili | Teams (IOI15_teams) | C++14 | 0 ms | 0 KiB |
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>
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
///#include "teams.h"
using namespace std;
const int INF = INT32_MAX;
int N, C[500005], A[500005], B[500005];
vector<int> P[500005];
struct node {
int val;
node *l, *r;
node() {
l = nullptr, r = nullptr; val = 0;
}
node(int 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, int l, int r, int pos, int x) {
if (l == r) return new node(v->val + x);
int 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);
}
}
int query(node* v, int l, int r, int lo, int hi) {
if (l > hi || r < lo) return 0;
if (l >= lo && r <= hi) return v->val;
int md = (l + r) / 2;
int a = 0, b = 0;
if(v -> l) a = query(v -> l, l, md, lo, hi);
if(v -> r) b = query(v -> r, md + 1, r, lo, hi);
return a + b;
}
int query(node* root, int lo, int hi) { return query(root, 1, N, lo, hi); }
void init(int n, int a[], int b[]) {
N = n; ST[0] = new node();
for(int l = 0; l < N; l++)
A[l] = a[l], B[l] = b[l];
for(int l = 0; l < N; l++)
P[A[l]].push_back(B[l]);
for(int 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);
}
}
int can(int M, int K[]) {
long long S = 0; vector<int> V;
for(int l = 0; l < M; l++) S += K[l];
if(S > N) return 0;
for(int l = 0; l < M; l++)
V.push_back(K[l]), C[K[l]]++;
sort(V.begin(), V.end());
V.erase(unique(V.begin(), V.end()), V.end());
vector<int> rem(V.size(), 0);
for(int i = 0; i < V.size(); i++) {
int U = V[i];
int cur = U * C[U];
for(int j = i; j < V.size(); j++) {
int hi = (j == V.size() - 1 ? N : V[j + 1] - 1);
int calc = min(cur, query(ST[U], 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;
}
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n; cin >> n; int a[n], b[n];
for(int l = 0; l < n; l++)
cin >> a[l] >> b[l];
int q; cin >> q; init(n, a, b);
while(q--) {
int m; cin >> m; int k[m];
for(int i = 0; i < m; i++)
cin >> k[i];
cout << can(m, k) << "\n";
}
return 0;
}#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
///#include "teams.h"
using namespace std;
const int INF = INT32_MAX;
int N, C[500005], A[500005], B[500005];
vector<int> P[500005];
struct node {
int val;
node *l, *r;
node() {
l = nullptr, r = nullptr; val = 0;
}
node(int 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, int l, int r, int pos, int x) {
if (l == r) return new node(v->val + x);
int 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);
}
}
int query(node* v, int l, int r, int lo, int hi) {
if (l > hi || r < lo) return 0;
if (l >= lo && r <= hi) return v->val;
int md = (l + r) / 2;
int a = 0, b = 0;
if(v -> l) a = query(v -> l, l, md, lo, hi);
if(v -> r) b = query(v -> r, md + 1, r, lo, hi);
return a + b;
}
int query(node* root, int lo, int hi) { return query(root, 1, N, lo, hi); }
void init(int n, int a[], int b[]) {
N = n; ST[0] = new node();
for(int l = 0; l < N; l++)
A[l] = a[l], B[l] = b[l];
for(int l = 0; l < N; l++)
P[A[l]].push_back(B[l]);
for(int 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);
}
}
int can(int M, int K[]) {
long long S = 0; vector<int> V;
for(int l = 0; l < M; l++) S += K[l];
if(S > N) return 0;
for(int l = 0; l < M; l++)
V.push_back(K[l]), C[K[l]]++;
sort(V.begin(), V.end());
V.erase(unique(V.begin(), V.end()), V.end());
vector<int> rem(V.size(), 0);
for(int i = 0; i < V.size(); i++) {
int U = V[i];
int cur = U * C[U];
for(int j = i; j < V.size(); j++) {
int hi = (j == V.size() - 1 ? N : V[j + 1] - 1);
int calc = min(cur, query(ST[U], 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;
}