Submission #637428

#	Time	Username	Problem	Language	Result	Execution time	Memory
637428		MohamedFaresNebili	Teams (IOI15_teams)	C++14	100 / 100	2400 ms	433144 KiB

teams

#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];
            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); }
 
            void init(int n, int a[], int b[]) {
                N = n; ST[0] = new node();
                map<int, int> occ[N + 1];
                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:89:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |                 for(int i = 0; i < V.size(); i++) {
      |                                ~~^~~~~~~~~~
teams.cpp:92:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |                     for(int j = i; j < V.size(); j++) {
      |                                    ~~^~~~~~~~~~
teams.cpp:93:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |                         int hi = (j == V.size() - 1 ? N : V[j + 1] - 1);
      |                                   ~~^~~~~~~~~~~~~~~

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