Submission #637390

#	Time	Username	Problem	Language	Result	Execution time	Memory
637390		MohamedFaresNebili	Teams (IOI15_teams)	C++14	0 / 100	1145 ms	398180 KiB

teams

#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);
                }
            }
            int 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;
            }

Compilation message (stderr)

teams.cpp: In constructor 'node::node(node*, node*)':
teams.cpp:20:28: warning: declaration of 'll' shadows a global declaration [-Wshadow]
   20 |                 node(node *ll, node *rr) {
      |                      ~~~~~~^~
teams.cpp:5:19: note: shadowed declaration is here
    5 |             using ll = long long;
      |                   ^~
teams.cpp: In constructor 'node::node(node*, node*)':
teams.cpp:20:28: warning: declaration of 'll' shadows a global declaration [-Wshadow]
   20 |                 node(node *ll, node *rr) {
      |                      ~~~~~~^~
teams.cpp:5:19: note: shadowed declaration is here
    5 |             using ll = long long;
      |                   ^~
teams.cpp: In constructor 'node::node(node*, node*)':
teams.cpp:20:28: warning: declaration of 'll' shadows a global declaration [-Wshadow]
   20 |                 node(node *ll, node *rr) {
      |                      ~~~~~~^~
teams.cpp:5:19: note: shadowed declaration is here
    5 |             using ll = long long;
      |                   ^~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:85:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |                 for(ll i = 0; i < V.size(); i++) {
      |                               ~~^~~~~~~~~~
teams.cpp:88:37: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |                     for(ll j = i; j < V.size(); j++) {
      |                                   ~~^~~~~~~~~~
teams.cpp:89:36: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |                         ll hi = (j == V.size() - 1 ? N : V[j + 1] - 1);
      |                                  ~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 21
• Subtask 2: 0 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23