oj.uz

Submission #429165

# Submission time Handle Problem Language Result Execution time Memory
429165 2021-06-15T18:01:30 Z timmyfeng Teams (IOI15_teams) C++17
100 / 100
 1459 ms 207264 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 500001, S = 64 * N;

int sum[S], child[S][2], ptr = 1;

int segtree(int x) {
    child[ptr][0] = child[ptr][1] = 0;
    sum[ptr] = x;
    return ptr++;
}

int segtree(int l, int r) {
    child[ptr][0] = l, child[ptr][1] = r;
    sum[ptr] = sum[l] + sum[r];
    return ptr++;
}

int build(int l, int r) {
    int u = segtree(0);
    if (l < r) {
        int m = (l + r) / 2;
        child[u][0] = build(l, m);
        child[u][1] = build(m + 1, r);
    }
    return u;
}

int update(int u, int a, int x, int l, int r) {
    if (l == r) {
        return segtree(sum[u] + x);
    } else {
        int m = (l + r) / 2;
        if (a <= m) {
            return segtree(update(child[u][0], a, x, l, m), child[u][1]);
        } else {
            return segtree(child[u][0], update(child[u][1], a, x, m + 1, r));
        }
    }
}

int copy(int u, int v, int a, int b, int l, int r) {
    if (b < a || b < l || r < a) {
        return v;
    } else if (a <= l && r <= b) {
        return u;
    } else {
        int m = (l + r) / 2;
        return segtree(
            copy(child[u][0], child[v][0], a, b, l, m),
            copy(child[u][1], child[v][1], a, b, m + 1, r)
        );
    }
}

int assign(int u, int v, int &k) {
    if (child[v][0] == 0) {
        int delta = min(k, sum[u] - sum[v]);
        k -= delta;
        return segtree(sum[v] + delta);
    } else if (sum[u] - sum[v] <= k) {
        k -= sum[u] - sum[v];
        return u;
    } else {
        int l = assign(child[u][0], child[v][0], k);
        int r = k > 0 ? assign(child[u][1], child[v][1], k) : child[v][1];
        return segtree(l, r);
    }
}

int root[N], n;
 
void init(int n, int a[], int b[]) {
    ::n = n;
    vector<array<int, 2>> students;
    for (int i = 0; i < n; ++i) {
        students.push_back({a[i], b[i]});
    }
    sort(students.begin(), students.end());
 
    root[0] = build(1, n);
    for (int i = 1, j = 0; i <= n; ++i) {
        root[i] = root[i - 1];
        while (j < n && students[j][0] == i) {
            root[i] = update(root[i], students[j++][1], 1, 1, n);
        }
    }
}
 
bool can(int m, int k[]) {
    int temp = ptr;
    sort(k, k + m);
    int used = root[0];
    for (int i = 0; i < m; ++i) {
        used = copy(root[k[i]], used, 1, k[i] - 1, 1, n);
        used = assign(root[k[i]], used, k[i]);
        if (k[i] > 0) {
            return false;
        }
    }
    ptr = temp;
    return true;
}

Compilation message

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:74:15: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   74 | void init(int n, int a[], int b[]) {
      |           ~~~~^
teams.cpp:72:14: note: shadowed declaration is here
   72 | int root[N], n;
      |              ^

Subtask #1
21.0 / 21.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 26644 KB Output is correct
2 Correct 79 ms 26680 KB Output is correct
3 Correct 74 ms 26636 KB Output is correct
4 Correct 73 ms 26772 KB Output is correct
5 Correct 48 ms 26204 KB Output is correct
6 Correct 38 ms 26208 KB Output is correct
7 Correct 40 ms 26204 KB Output is correct
8 Correct 40 ms 26232 KB Output is correct
9 Correct 58 ms 37704 KB Output is correct
10 Correct 49 ms 31184 KB Output is correct
11 Correct 37 ms 26504 KB Output is correct
12 Correct 36 ms 25356 KB Output is correct
13 Correct 68 ms 26764 KB Output is correct
14 Correct 45 ms 25864 KB Output is correct
15 Correct 61 ms 26552 KB Output is correct
16 Correct 67 ms 26680 KB Output is correct
17 Correct 44 ms 26824 KB Output is correct
18 Correct 43 ms 26936 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 26876 KB Output is correct
2 Correct 82 ms 26820 KB Output is correct
3 Correct 265 ms 38576 KB Output is correct
4 Correct 77 ms 26860 KB Output is correct
5 Correct 74 ms 26424 KB Output is correct
6 Correct 73 ms 32176 KB Output is correct
7 Correct 46 ms 26440 KB Output is correct
8 Correct 67 ms 30500 KB Output is correct
9 Correct 59 ms 37584 KB Output is correct
10 Correct 79 ms 31548 KB Output is correct
11 Correct 82 ms 27036 KB Output is correct
12 Correct 98 ms 28420 KB Output is correct
13 Correct 183 ms 41972 KB Output is correct
14 Correct 321 ms 41640 KB Output is correct
15 Correct 115 ms 36760 KB Output is correct
16 Correct 106 ms 36772 KB Output is correct
17 Correct 83 ms 35320 KB Output is correct
18 Correct 87 ms 36544 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 617 ms 139992 KB Output is correct
2 Correct 648 ms 140668 KB Output is correct
3 Correct 1308 ms 171044 KB Output is correct
4 Correct 611 ms 145884 KB Output is correct
5 Correct 330 ms 143116 KB Output is correct
6 Correct 297 ms 153632 KB Output is correct
7 Correct 228 ms 143148 KB Output is correct
8 Correct 292 ms 148704 KB Output is correct
9 Correct 340 ms 207264 KB Output is correct
10 Correct 305 ms 147864 KB Output is correct
11 Correct 342 ms 142556 KB Output is correct
12 Correct 442 ms 147772 KB Output is correct
13 Correct 828 ms 176892 KB Output is correct
14 Correct 1459 ms 177592 KB Output is correct
15 Correct 617 ms 165928 KB Output is correct
16 Correct 585 ms 164208 KB Output is correct
17 Correct 340 ms 163484 KB Output is correct
18 Correct 337 ms 163156 KB Output is correct