Submission #637430

#TimeUsernameProblemLanguageResultExecution timeMemory
637430MohamedFaresNebiliTeams (IOI15_teams)C++14
100 / 100
2248 ms439560 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") ///#include "teams.h" using namespace std; const int INF = INT32_MAX; int N, C[500005], A[500005], B[500005]; int pref[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); } map<int, int> occ[500005]; 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]; occ[A[l]][B[l]]++; pref[A[l]]++; pref[B[l] + 1]--; } 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 : occ[l]) ST[l] = update(ST[l], 1, N, u.first, u.second); } for(int l = 1; l <= N; l++) pref[l] += pref[l - 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(pref[K[l]] < K[l]) return 0; } 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; }

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:90:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |                 for(int i = 0; i < V.size(); i++) {
      |                                ~~^~~~~~~~~~
teams.cpp:93:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |                     for(int j = i; j < V.size(); j++) {
      |                                    ~~^~~~~~~~~~
teams.cpp:94:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |                         int hi = (j == V.size() - 1 ? N : V[j + 1] - 1);
      |                                   ~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...