oj.uz

Submission #637404

# Submission time Handle Problem Language Result Execution time Memory
637404 2022-09-01T16:08:08 Z MohamedFaresNebili Teams (IOI15_teams) C++14
100 / 100
 2733 ms 391400 KB 
#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);
                }
            }

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

Compilation message

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

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 12116 KB Output is correct
4 Correct 6 ms 12116 KB Output is correct
5 Correct 6 ms 12116 KB Output is correct
6 Correct 6 ms 12116 KB Output is correct
7 Correct 6 ms 12008 KB Output is correct
8 Correct 6 ms 12116 KB Output is correct
9 Correct 6 ms 12116 KB Output is correct
10 Correct 6 ms 12116 KB Output is correct
11 Correct 6 ms 11988 KB Output is correct
12 Correct 7 ms 12116 KB Output is correct
13 Correct 6 ms 12116 KB Output is correct
14 Correct 6 ms 12100 KB Output is correct
15 Correct 6 ms 12116 KB Output is correct
16 Correct 6 ms 12116 KB Output is correct
17 Correct 6 ms 11988 KB Output is correct
18 Correct 8 ms 11988 KB Output is correct
19 Correct 7 ms 11988 KB Output is correct
20 Correct 6 ms 11988 KB Output is correct
21 Correct 6 ms 11988 KB Output is correct
22 Correct 7 ms 11988 KB Output is correct
23 Correct 7 ms 11988 KB Output is correct
24 Correct 6 ms 11988 KB Output is correct
25 Correct 6 ms 11988 KB Output is correct
26 Correct 7 ms 11988 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 79136 KB Output is correct
2 Correct 118 ms 79160 KB Output is correct
3 Correct 117 ms 79056 KB Output is correct
4 Correct 122 ms 80192 KB Output is correct
5 Correct 71 ms 73452 KB Output is correct
6 Correct 70 ms 73548 KB Output is correct
7 Correct 69 ms 73540 KB Output is correct
8 Correct 74 ms 73540 KB Output is correct
9 Correct 72 ms 71620 KB Output is correct
10 Correct 82 ms 71364 KB Output is correct
11 Correct 70 ms 74312 KB Output is correct
12 Correct 70 ms 71232 KB Output is correct
13 Correct 77 ms 74920 KB Output is correct
14 Correct 85 ms 74824 KB Output is correct
15 Correct 108 ms 78468 KB Output is correct
16 Correct 107 ms 78540 KB Output is correct
17 Correct 75 ms 74876 KB Output is correct
18 Correct 79 ms 74716 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 79492 KB Output is correct
2 Correct 153 ms 79460 KB Output is correct
3 Correct 211 ms 82868 KB Output is correct
4 Correct 121 ms 80124 KB Output is correct
5 Correct 87 ms 73932 KB Output is correct
6 Correct 85 ms 73896 KB Output is correct
7 Correct 79 ms 73940 KB Output is correct
8 Correct 87 ms 73964 KB Output is correct
9 Correct 71 ms 71596 KB Output is correct
10 Correct 70 ms 71680 KB Output is correct
11 Correct 84 ms 74672 KB Output is correct
12 Correct 821 ms 71632 KB Output is correct
13 Correct 255 ms 75344 KB Output is correct
14 Correct 242 ms 80428 KB Output is correct
15 Correct 132 ms 78936 KB Output is correct
16 Correct 127 ms 78988 KB Output is correct
17 Correct 91 ms 75256 KB Output is correct
18 Correct 91 ms 75140 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 875 ms 383488 KB Output is correct
2 Correct 910 ms 383520 KB Output is correct
3 Correct 1089 ms 391400 KB Output is correct
4 Correct 797 ms 384816 KB Output is correct
5 Correct 401 ms 355376 KB Output is correct
6 Correct 401 ms 355276 KB Output is correct
7 Correct 371 ms 355276 KB Output is correct
8 Correct 379 ms 355356 KB Output is correct
9 Correct 331 ms 341096 KB Output is correct
10 Correct 348 ms 355408 KB Output is correct
11 Correct 1082 ms 355216 KB Output is correct
12 Correct 2733 ms 355604 KB Output is correct
13 Correct 1053 ms 359304 KB Output is correct
14 Correct 1083 ms 381900 KB Output is correct
15 Correct 711 ms 377840 KB Output is correct
16 Correct 696 ms 378020 KB Output is correct
17 Correct 433 ms 357868 KB Output is correct
18 Correct 439 ms 357844 KB Output is correct