oj.uz

Submission #726709

# Submission time Handle Problem Language Result Execution time Memory
726709 2023-04-19T09:21:31 Z becaido Teams (IOI15_teams) C++17
100 / 100
 708 ms 145600 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifndef WAIMAI
#include "teams.h"
#endif

const int SIZE = 5e5 + 5;
const int H = __lg(SIZE) + 1;

int n;
int id[SIZE];
pair<int, int> p[SIZE];

struct Node {
    int sum, ls, rs;
} node[4 * SIZE * H];

int sz, root[SIZE];
int newnode() {
    sz++;
    node[sz].sum = node[sz].ls = node[sz].rs = 0;
    return sz;
}

void build(int &pos, int l, int r) {
    pos = newnode();
    if (l == r) return;
    int mid = (l + r) / 2;
    build(node[pos].ls, l, mid);
    build(node[pos].rs, mid + 1, r);
}

void upd(int &pos, int l, int r, int p) {
    node[newnode()] = node[pos];
    pos = sz;
    if (l == r) {
        node[pos].sum++;
        return;
    }
    int mid = (l + r) / 2;
    if (p <= mid) upd(node[pos].ls, l, mid, p);
    else upd(node[pos].rs, mid + 1, r, p);
    node[pos].sum = node[node[pos].ls].sum + node[node[pos].rs].sum;
}

int que(int pl, int pr, int l, int r, int L, int R) {
    if (l == L && r == R) return node[pr].sum - node[pl].sum;
    int mid = (L + R) / 2;
    if (r <= mid) return que(node[pl].ls, node[pr].ls, l, r, L, mid);
    if (l > mid) return que(node[pl].rs, node[pr].rs, l, r, mid + 1, R);
    return que(node[pl].ls, node[pr].ls, l, mid, L, mid) + que(node[pl].rs, node[pr].rs, mid + 1, r, mid + 1, R);
}

void init(int N, int A[], int B[]) {
    n = N;
    sz = 0;
    for (int i = 1; i <= n; i++) p[i] = {A[i - 1], B[i - 1]};
    sort(p + 1, p + n + 1);
    build(root[0], 1, n);
    int rp = 1;
    for (int i = 1; i <= n; i++) {
        root[i] = root[i - 1];
        while (rp <= n && p[rp].first == i) upd(root[i], 1, n, p[rp].second), rp++;
    }
}

const int lim = 5e4;
const int magic = 3;
int dp[lim + 5];
int can(int M, int K[]) {
    sort(K, K + M);
    if (M <= lim) {
        for (int i = 0; i < M; i++) {
            dp[i] = que(root[0], root[K[i]], K[i], n, 1, n) - K[i];
            for (int j = max(0, i - magic); j < i && dp[i] >= 0; j++) dp[i] = min(dp[i], dp[j] + que(root[K[j]], root[K[i]], K[i], n, 1, n) - K[i]);
            if (dp[i] < 0) return 0;
        }
        return 1;
    }
    priority_queue<int, vector<int>, greater<int>> pq;
    int rp = 1;
    for (int i = 0; i < M; i++) {
        while (rp <= n && p[rp].first <= K[i]) pq.push(p[rp].second), rp++;
        while (pq.size() && pq.top() < K[i]) pq.pop();
        if (pq.size() < K[i]) return 0;
        for (int j = 1; j <= K[i]; j++) pq.pop();
    }
    return 1;
}

#ifdef WAIMAI
int main() {
    int N;
    cin >> N;
    int *A = (int*)malloc(sizeof(int)*(unsigned int)N);
    int *B = (int*)malloc(sizeof(int)*(unsigned int)N);
    for (int i = 0; i < N; ++i) cin >> A[i] >> B[i];
    init(N, A, B);
    int Q;
    cin >> Q;
    for (int i = 0; i < Q; ++i) {
    	int M;
    	cin >> M;
	int *K = (int*)malloc(sizeof(int)*(unsigned int)M);
    	for (int j = 0; j < M; ++j) {
    		cin >> K[j];
    	}
    	cout << can(M, K) << '\n';
    }
    return 0;
}
#endif

Compilation message

teams.cpp: In function 'void upd(int&, int, int, int)':
teams.cpp:36:38: warning: declaration of 'p' shadows a global declaration [-Wshadow]
   36 | void upd(int &pos, int l, int r, int p) {
      |                                  ~~~~^
teams.cpp:15:16: note: shadowed declaration is here
   15 | pair<int, int> p[SIZE];
      |                ^
teams.cpp: In function 'int can(int, int*)':
teams.cpp:88:23: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int, std::vector<int>, std::greater<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   88 |         if (pq.size() < K[i]) return 0;
      |             ~~~~~~~~~~^~~~~~

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 1 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 0 ms 340 KB Output is correct
12 Correct 2 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 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 0 ms 340 KB Output is correct
26 Correct 1 ms 212 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 25332 KB Output is correct
2 Correct 64 ms 25304 KB Output is correct
3 Correct 68 ms 25352 KB Output is correct
4 Correct 70 ms 25740 KB Output is correct
5 Correct 45 ms 25404 KB Output is correct
6 Correct 45 ms 25292 KB Output is correct
7 Correct 46 ms 25320 KB Output is correct
8 Correct 42 ms 25284 KB Output is correct
9 Correct 57 ms 24812 KB Output is correct
10 Correct 40 ms 24628 KB Output is correct
11 Correct 41 ms 25740 KB Output is correct
12 Correct 37 ms 24468 KB Output is correct
13 Correct 51 ms 25624 KB Output is correct
14 Correct 48 ms 24820 KB Output is correct
15 Correct 59 ms 25320 KB Output is correct
16 Correct 64 ms 25316 KB Output is correct
17 Correct 43 ms 25652 KB Output is correct
18 Correct 44 ms 25688 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 25748 KB Output is correct
2 Correct 79 ms 25716 KB Output is correct
3 Correct 145 ms 28612 KB Output is correct
4 Correct 76 ms 25692 KB Output is correct
5 Correct 94 ms 25732 KB Output is correct
6 Correct 95 ms 25712 KB Output is correct
7 Correct 55 ms 25760 KB Output is correct
8 Correct 78 ms 25872 KB Output is correct
9 Correct 51 ms 24748 KB Output is correct
10 Correct 78 ms 25060 KB Output is correct
11 Correct 80 ms 26052 KB Output is correct
12 Correct 84 ms 24968 KB Output is correct
13 Correct 113 ms 26160 KB Output is correct
14 Correct 136 ms 27244 KB Output is correct
15 Correct 96 ms 25764 KB Output is correct
16 Correct 97 ms 25804 KB Output is correct
17 Correct 79 ms 26152 KB Output is correct
18 Correct 80 ms 26120 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 432 ms 139684 KB Output is correct
2 Correct 443 ms 139760 KB Output is correct
3 Correct 708 ms 145600 KB Output is correct
4 Correct 433 ms 139668 KB Output is correct
5 Correct 331 ms 139672 KB Output is correct
6 Correct 347 ms 139740 KB Output is correct
7 Correct 238 ms 139748 KB Output is correct
8 Correct 302 ms 139764 KB Output is correct
9 Correct 224 ms 136144 KB Output is correct
10 Correct 293 ms 140112 KB Output is correct
11 Correct 305 ms 139980 KB Output is correct
12 Correct 322 ms 140012 KB Output is correct
13 Correct 471 ms 140112 KB Output is correct
14 Correct 694 ms 142108 KB Output is correct
15 Correct 444 ms 139988 KB Output is correct
16 Correct 424 ms 139940 KB Output is correct
17 Correct 287 ms 140068 KB Output is correct
18 Correct 277 ms 140056 KB Output is correct