Submission #637388

#	Time	Username	Problem	Language	Result	Execution time	Memory
637388		MohamedFaresNebili	Teams (IOI15_teams)	C++14	0 / 100	1107 ms	399884 KiB

teams

#include <bits/stdc++.h>
#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);
                }
            }

            node* emp;
            int query(node* v, node* v0, int l, int r, int lo, int hi) {
                if (l > hi || r < lo) return 0;
                if (l >= lo && r <= hi) return v->val - v0->val;
                int md = (l + r) / 2;

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

            int query(node* root, node* root0, int lo, int 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(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[]) {
                int S = 0;
                for(int l = 0; l < M; l++) S += K[l];
                if(S > N) return 0;
                vector<int> V;
                for(int 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<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], 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 function 'int can(int, int*)':
teams.cpp:84:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |                 for(int i = 0; i < V.size(); i++) {
      |                                ~~^~~~~~~~~~
teams.cpp:87:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |                     for(int j = i; j < V.size(); j++) {
      |                                    ~~^~~~~~~~~~
teams.cpp:88:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |                         int 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