oj.uz

Submission #637430

# Submission time Handle Problem Language Result Execution time Memory
637430 2022-09-01T17:16:04 Z MohamedFaresNebili Teams (IOI15_teams) C++14
100 / 100
 2248 ms 439560 KB 
#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

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);
      |                                   ~~^~~~~~~~~~~~~~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 35540 KB Output is correct
2 Correct 19 ms 35540 KB Output is correct
3 Correct 19 ms 35544 KB Output is correct
4 Correct 19 ms 35540 KB Output is correct
5 Correct 19 ms 35540 KB Output is correct
6 Correct 18 ms 35628 KB Output is correct
7 Correct 18 ms 35540 KB Output is correct
8 Correct 18 ms 35576 KB Output is correct
9 Correct 19 ms 35540 KB Output is correct
10 Correct 19 ms 35540 KB Output is correct
11 Correct 18 ms 35532 KB Output is correct
12 Correct 18 ms 35580 KB Output is correct
13 Correct 19 ms 35576 KB Output is correct
14 Correct 20 ms 35544 KB Output is correct
15 Correct 19 ms 35540 KB Output is correct
16 Correct 18 ms 35540 KB Output is correct
17 Correct 19 ms 35572 KB Output is correct
18 Correct 18 ms 35540 KB Output is correct
19 Correct 19 ms 35508 KB Output is correct
20 Correct 19 ms 35520 KB Output is correct
21 Correct 19 ms 35488 KB Output is correct
22 Correct 19 ms 35540 KB Output is correct
23 Correct 18 ms 35544 KB Output is correct
24 Correct 18 ms 35564 KB Output is correct
25 Correct 18 ms 35540 KB Output is correct
26 Correct 19 ms 35572 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 107736 KB Output is correct
2 Correct 154 ms 107836 KB Output is correct
3 Correct 153 ms 107596 KB Output is correct
4 Correct 157 ms 108644 KB Output is correct
5 Correct 29 ms 42288 KB Output is correct
6 Correct 28 ms 42188 KB Output is correct
7 Correct 29 ms 42336 KB Output is correct
8 Correct 28 ms 42308 KB Output is correct
9 Correct 28 ms 42416 KB Output is correct
10 Correct 27 ms 42072 KB Output is correct
11 Correct 27 ms 41872 KB Output is correct
12 Correct 31 ms 42496 KB Output is correct
13 Correct 50 ms 54216 KB Output is correct
14 Correct 83 ms 74400 KB Output is correct
15 Correct 144 ms 96044 KB Output is correct
16 Correct 139 ms 96076 KB Output is correct
17 Correct 35 ms 43860 KB Output is correct
18 Correct 34 ms 43860 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 108008 KB Output is correct
2 Correct 166 ms 108008 KB Output is correct
3 Correct 197 ms 111240 KB Output is correct
4 Correct 162 ms 108728 KB Output is correct
5 Correct 46 ms 42668 KB Output is correct
6 Correct 39 ms 42580 KB Output is correct
7 Correct 40 ms 42700 KB Output is correct
8 Correct 40 ms 42648 KB Output is correct
9 Correct 27 ms 42316 KB Output is correct
10 Correct 30 ms 42316 KB Output is correct
11 Correct 42 ms 42264 KB Output is correct
12 Correct 772 ms 42888 KB Output is correct
13 Correct 208 ms 54800 KB Output is correct
14 Correct 252 ms 107088 KB Output is correct
15 Correct 154 ms 96528 KB Output is correct
16 Correct 146 ms 96492 KB Output is correct
17 Correct 49 ms 44272 KB Output is correct
18 Correct 50 ms 44300 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1046 ms 432404 KB Output is correct
2 Correct 1043 ms 432660 KB Output is correct
3 Correct 1176 ms 439560 KB Output is correct
4 Correct 1103 ms 433584 KB Output is correct
5 Correct 107 ms 68980 KB Output is correct
6 Correct 93 ms 69088 KB Output is correct
7 Correct 97 ms 68996 KB Output is correct
8 Correct 91 ms 69024 KB Output is correct
9 Correct 70 ms 69168 KB Output is correct
10 Correct 75 ms 67900 KB Output is correct
11 Correct 818 ms 68120 KB Output is correct
12 Correct 2248 ms 71916 KB Output is correct
13 Correct 770 ms 136816 KB Output is correct
14 Correct 1251 ms 421372 KB Output is correct
15 Correct 753 ms 315060 KB Output is correct
16 Correct 766 ms 314976 KB Output is correct
17 Correct 165 ms 78280 KB Output is correct
18 Correct 130 ms 78244 KB Output is correct