Submission #726709

#	Time	Username	Problem	Language	Result	Execution time	Memory
726709		becaido	Teams (IOI15_teams)	C++17	100 / 100	708 ms	145600 KiB

teams

#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 (stderr)

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 / 21
• Subtask 2: 13 / 13
• Subtask 3: 43 / 43
• Subtask 4: 23 / 23