Submission #256022

#	Time	Username	Problem	Language	Result	Execution time	Memory
256022		dolphingarlic	Teams (IOI15_teams)	C++14	0 / 100	189 ms	86520 KiB

teams

#include "teams.h"

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
using namespace std;

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

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;
pair<int, int> s[500000], min_max[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 > a || r < b) 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]};
    sort(s, s + n, [](pair<int, int> X, pair<int, int> Y) {
        return X.second < Y.second;
    });
    for (int i = 0; i < n; i += B_SIZE) {
        sort(s + i, s + min(n, i + B_SIZE));
        min_max[i / B_SIZE] = {INT_MAX, INT_MIN};
    }
    for (int i = 0; i < n; i++) {
        min_max[i / B_SIZE].first =
            min(min_max[i / B_SIZE].first, s[i].second);
        min_max[i / B_SIZE].second =
            max(min_max[i / B_SIZE].second, s[i].second);
    }
    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) {
            if (min_max[j / B_SIZE].first < K[i] && min_max[j / B_SIZE].second < K[i]) {
                continue;
            } else if (min_max[j / B_SIZE].first < K[i] && min_max[j / B_SIZE].second >= K[i]) {
                for (int k = j; k < j + B_SIZE && cnt != K[i]; k++) {
                    if (s[k].first <= K[i] && s[k].second >= K[i] && query(curr, k, k)) {
                        cnt++;
                        curr = update(curr, k, k);
                    }
                }
                if (cnt == K[i]) break;
            } else {
                int idx = upper_bound(s + j, s + min(n, j + B_SIZE), make_pair(K[i], INT_MAX)) - s - j - 1;
                int available = query(curr, j, idx);
                if (cnt + available < K[i]) {
                    cnt += available;
                    curr = update(curr, j, idx);
                } else {
                    for (int k = j; k < j + B_SIZE && cnt != K[i]; k++) {
                        if (query(curr, k, k)) {
                            cnt++;
                            curr = update(curr, k, k);
                        }
                    }
                    break;
                }
            }
        }
        if (cnt != K[i]) return 0;
    }
    return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:83:104: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
                 int idx = upper_bound(s + j, s + min(n, j + B_SIZE), make_pair(K[i], INT_MAX)) - s - j - 1;
                           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~

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