제출 #256110

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
256110		dolphingarlic	Teams (IOI15_teams)	C++14	21 / 100	2234 ms	524292 KiB

teams

/*
IOI 2015 Teams
- Base strategy:
    - Sort students by B
    - Sort the teams by size
    - For each team, choose the K[i] available students with minimum B
- To mark students as used for multiple queries, use a persistent segtree
  with range query and range paint
- To process students efficiently, use sqrt decomposition:
    - Sort as before
    - Split the students into sqrt(N) buckets
    - For each bucket, sort by A
    - For any team and bucket, we have 3 cases:
        - Case 1: All students in the current bucket have B < K[i]
            - We can't choose any students, so we just continue
        - Case 2: Some students in the current bucket have B < K[i]
                  and others have B >= K[i]
            - This case happens at most once per team, so just iterate
              through the bucket and choose the available students with
              minimum B
        - Case 3: All students in the current bucket have B >= K[i]
            - We use std::upper_bound to find the range of students
              with A <= K[i]
            - If (available students in range) + (previously taken students) < K[i],
              take all available students in the range
            - Otherwise, we can just do what we did for case 2 again
- Complexity: O(S sqrt(N) log N)
*/

#include "teams.h"

#include <bits/stdc++.h>
using namespace std;

const int B_SIZE = 750;  // N.B. No less than 708

struct Student {
    int A, B, idx;
    bool good(int K) { return A <= K && K <= B; }
};

bool operator<(Student x, Student y) {
    if (x.A == y.A) return x.B < y.B;
    return x.A < y.A;
}
bool b_cmp(Student x, Student y) {
    if (x.B == y.B) return x.A < y.A;
    return x.B < y.B;
}

// Persistent segtree with range query and range paint
struct Node {
    int val;
    Node *l, *r;

    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) {}
};

int n;
Student s[500000];
pair<int, int> mn_mx[B_SIZE];
Node *orig, *curr;

Node *build(int l = 0, int r = n - 1) {
    if (l == r) return new Node(1);
    int mid = (l + r) / 2;
    return new Node(build(l, mid), build(mid + 1, r));
}

Node *update(Node *node, int a, int b, int l = 0, int r = n - 1) {
    if (l > b || r < a) return node;
    if (l >= a && r <= b) return new Node(0);
    int mid = (l + r) / 2;
    return new Node(update(node->l, a, b, l, mid), update(node->r, a, b, mid + 1, r));
}

int query(Node *node, int a, int b, int l = 0, int r = n - 1) {
    if (!node->val || l > b || r < a) return 0;
    if (l >= a && r <= b) return node->val;
    int mid = (l + r) / 2;
    return query(node->l, a, b, l, mid) + query(node->r, a, b, mid + 1, r);
}

void init(int N, int A[], int B[]) {
    n = N;
    for (int i = 0; i < n; i++) s[i] = {A[i], B[i], -1};
    sort(s, s + n, b_cmp);
    for (int i = 0; i < n; i += B_SIZE) {
        sort(s + i, s + min(n, i + B_SIZE));
        int b = i / B_SIZE;
        mn_mx[b] = {INT_MAX, INT_MIN};
        for (int j = i; j < min(n, i + B_SIZE); j++) {
            s[j].idx = j;
            mn_mx[b] = {min(mn_mx[b].first, s[j].B), max(mn_mx[b].second, s[j].B)};
        }
    }
    orig = build();
}

int can(int M, int K[]) {
    sort(K, K + M);
    curr = new Node(orig);
    for (int i = 0; i < M; i++) {
        int cnt = 0;
        for (int j = 0; j < n; j += B_SIZE) {
            // Case 1: All students in the current bucket have B < K[i]
            if (mn_mx[j / B_SIZE].second < K[i]) continue;
            // Case 2: Some students in the current bucket have B < K[i] and others have B >= K[i]
            else if (mn_mx[j / B_SIZE].first < K[i] && mn_mx[j / B_SIZE].second >= K[i]) {
                // Choose the available students in this bucket with the minimum B
                sort(s + j, s + min(n, j + B_SIZE), b_cmp);
                // Just go through the entire bucket for this since it happens at most once per team
                for (int k = j; k < min(n, j + B_SIZE) && cnt != K[i]; k++) {
                    if (s[k].good(K[i]) && query(curr, s[k].idx, s[k].idx)) {
                        cnt++;
                        curr = update(curr, s[k].idx, s[k].idx);
                    }
                }
                sort(s + j, s + min(n, j + B_SIZE));
                if (cnt == K[i]) break;
            }
            // Case 3: All students in the current bucket have B >= K[i]
            else {
                Student tmp = {K[i], INT_MAX, -1};
                // All students in the range [j, idx] are good for the current team
                int idx = int(upper_bound(s + j, s + min(n, j + B_SIZE), tmp) - s) - j - 1;
                int available = query(curr, j, j + idx);
                if (cnt + available < K[i]) {
                    // Choose all available students in this bucket
                    cnt += available;
                    curr = update(curr, j, j + idx);
                } else {
                    // Choose the available students in this bucket with the minimum B
                    sort(s + j, s + min(n, j + B_SIZE), b_cmp);
                    // Just go through the entire bucket for this since it happens at most once per team
                    for (int k = j; k < min(n, j + B_SIZE) && cnt != K[i]; k++) {
                        if (s[k].good(K[i]) && query(curr, s[k].idx, s[k].idx)) {
                            cnt++;
                            curr = update(curr, s[k].idx, s[k].idx);
                        }
                    }
                    sort(s + j, s + min(n, j + B_SIZE));
                    if (cnt == K[i]) break;
                }
            }
        }
        if (cnt != K[i]) return 0;
    }
    return 1;
}

• Subtask 1: 21 / 21
• Subtask 2: 0 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23