oj.uz

Submission #564717

# Submission time Handle Problem Language Result Execution time Memory
564717 2022-05-19T13:57:37 Z hoanghq2004 Teams (IOI15_teams) C++14
100 / 100
 3389 ms 149260 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "teams.h"

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 5e5 + 10;

int n;
int root[N];

struct node {
    int lhs, rhs;
    int cnt;
} st[N * 40];

int nNode = 0;
int add(int id, int L, int R, int i) {
    if (L == R) {
        st[++nNode] = st[id];
        ++st[nNode].cnt;
        return nNode;
    }
    int cur = ++nNode;
    st[cur] = st[id];
    int mid = L + R >> 1;
    if (i <= mid) st[cur].lhs = add(st[id].lhs, L, mid, i);
    else st[cur].rhs = add(st[id].rhs, mid + 1, R, i);
    st[cur].cnt = st[st[cur].lhs].cnt + st[st[cur].rhs].cnt;
    return cur;
}
int get(int id, int L, int R, int u, int v) {
    if (u > R || L > v) return 0;
    if (u <= L && R <= v) return st[id].cnt;
    int mid = L + R >> 1;
    return get(st[id].lhs, L, mid, u, v) + get(st[id].rhs, mid + 1, R, u, v);
}


void init(int _n, int A[], int B[]) {
    n = _n;
    vector <vector <int>> s(n + 1);
    for (int i = 0; i < n; ++i) s[B[i]].push_back(A[i]);
    for (int i = 1; i <= n; ++i) {
        int r = root[i - 1];
        for (auto val: s[i]) r = add(r, 1, n, val);
        root[i] = r;
    }
}

int cnt[N];

int can(int m, int x[]) {
    map <int, int> mp;
    long long tot = 0;
    for (int i = 0; i < m; ++i) tot += x[i];
    if (tot > n) return 0;
    for (int i = 0; i < m; ++i) mp[x[i]] += x[i];
    vector <int> List;
    for (auto [x, need]: mp) List.push_back(x);
    List.push_back(n + 1);
    for (int i = 0; i < List.size() - 1; ++i) cnt[i] = 0;
    for (int i = 0; i + 1 < List.size(); ++i) {
        int need = mp[List[i]];
        for (int j = i; j + 1 < List.size(); ++j) {
            int cur = get(root[List[j + 1] - 1], 1, n, 1, List[i]) - get(root[List[j] - 1], 1, n, 1, List[i]);
            cur -= cnt[j];
            int delta = min(cur, need);
            need -= delta;
            cnt[j] += delta;
            if (need == 0) break;
        }
        if (need != 0) return 0;
    }
    return 1;
}

Compilation message

teams.cpp: In function 'int add(int, int, int, int)':
teams.cpp:33:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |     int mid = L + R >> 1;
      |               ~~^~~
teams.cpp: In function 'int get(int, int, int, int, int)':
teams.cpp:42:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |     int mid = L + R >> 1;
      |               ~~^~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:67:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   67 |     for (auto [x, need]: mp) List.push_back(x);
      |               ^
teams.cpp:67:16: warning: declaration of 'auto x' shadows a parameter [-Wshadow]
   67 |     for (auto [x, need]: mp) List.push_back(x);
      |                ^
teams.cpp:60:20: note: shadowed declaration is here
   60 | int can(int m, int x[]) {
      |                ~~~~^~~
teams.cpp:69:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for (int i = 0; i < List.size() - 1; ++i) cnt[i] = 0;
      |                     ~~^~~~~~~~~~~~~~~~~
teams.cpp:70:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for (int i = 0; i + 1 < List.size(); ++i) {
      |                     ~~~~~~^~~~~~~~~~~~~
teams.cpp:72:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         for (int j = i; j + 1 < List.size(); ++j) {
      |                         ~~~~~~^~~~~~~~~~~~~

Subtask #1
21.0 / 21.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 26400 KB Output is correct
2 Correct 51 ms 26316 KB Output is correct
3 Correct 54 ms 26376 KB Output is correct
4 Correct 55 ms 26352 KB Output is correct
5 Correct 29 ms 25364 KB Output is correct
6 Correct 28 ms 25288 KB Output is correct
7 Correct 29 ms 25304 KB Output is correct
8 Correct 29 ms 25192 KB Output is correct
9 Correct 29 ms 25404 KB Output is correct
10 Correct 28 ms 25428 KB Output is correct
11 Correct 28 ms 25492 KB Output is correct
12 Correct 28 ms 25428 KB Output is correct
13 Correct 33 ms 25284 KB Output is correct
14 Correct 37 ms 25816 KB Output is correct
15 Correct 48 ms 26200 KB Output is correct
16 Correct 46 ms 26240 KB Output is correct
17 Correct 30 ms 25464 KB Output is correct
18 Correct 30 ms 25468 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 26372 KB Output is correct
2 Correct 123 ms 26284 KB Output is correct
3 Correct 131 ms 26376 KB Output is correct
4 Correct 51 ms 26324 KB Output is correct
5 Correct 70 ms 25300 KB Output is correct
6 Correct 71 ms 25296 KB Output is correct
7 Correct 62 ms 25216 KB Output is correct
8 Correct 66 ms 25300 KB Output is correct
9 Correct 29 ms 25420 KB Output is correct
10 Correct 31 ms 25548 KB Output is correct
11 Correct 71 ms 25488 KB Output is correct
12 Correct 1128 ms 25364 KB Output is correct
13 Correct 202 ms 25292 KB Output is correct
14 Correct 140 ms 26148 KB Output is correct
15 Correct 84 ms 26136 KB Output is correct
16 Correct 83 ms 26268 KB Output is correct
17 Correct 59 ms 25500 KB Output is correct
18 Correct 57 ms 25480 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 562 ms 143988 KB Output is correct
2 Correct 549 ms 143936 KB Output is correct
3 Correct 619 ms 144004 KB Output is correct
4 Correct 406 ms 144032 KB Output is correct
5 Correct 241 ms 138108 KB Output is correct
6 Correct 237 ms 142148 KB Output is correct
7 Correct 224 ms 142156 KB Output is correct
8 Correct 238 ms 142284 KB Output is correct
9 Correct 154 ms 141936 KB Output is correct
10 Correct 153 ms 140132 KB Output is correct
11 Correct 2023 ms 140652 KB Output is correct
12 Correct 3389 ms 140992 KB Output is correct
13 Correct 808 ms 143244 KB Output is correct
14 Correct 715 ms 149260 KB Output is correct
15 Correct 500 ms 149024 KB Output is correct
16 Correct 467 ms 149156 KB Output is correct
17 Correct 277 ms 143820 KB Output is correct
18 Correct 239 ms 143840 KB Output is correct