Submission #1172844

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172844		anmattroi	Teams (IOI15_teams)	C++17	0 / 100	1008 ms	541984 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
#define maxn 500005
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;

int n;
int a[maxn], b[maxn];

struct node {
    int val = 0;
    node *left_child = nullptr, *right_child = nullptr;
    node() {}
    node(int _val) : val(_val) {}

    void extend_left() {
        if (left_child == nullptr) left_child = new node();
    }
    void extend_right() {
        if (right_child == nullptr) right_child = new node();
    }
};

node* root[maxn];
node* er;

node* build(int lo = 1, int hi = n) {
    if (lo == hi) return new node();
    node *cur = new node();
    int mid = (lo + hi) >> 1;
    cur->left_child = build(lo, mid);
    cur->right_child = build(mid+1, hi);
    return cur;
}

node* upd(int u, node *oldver, int lo = 1, int hi = n) {
    if (lo == hi)
        return new node(oldver->val + 1);

    node *cur = new node();
    int mid = (lo + hi) >> 1;
    if (u <= mid) {
        cur->left_child = upd(u, oldver->left_child, lo, mid);
        cur->right_child = oldver->right_child;
    } else {
        cur->left_child = oldver->left_child;
        cur->right_child = upd(u, oldver->right_child, mid+1, hi);
    }
    cur->val = cur->left_child->val + cur->right_child->val;

    return cur;
}

//int get(int u, int v, node *cur, int lo = 1, int hi = n) {
//    if (u <= lo && hi <= v) return cur->val;
//    int mid = (lo + hi) >> 1;
//    return (u <= mid ? get(u, v, cur->left_child, lo, mid) : 0) +
//           (v > mid ? get(u, v, cur->right_child, mid+1, hi) : 0);
//}
void preprocess() {
    vector<vector<int> > nho(n+1);
    for (int i = 0; i < n; i++)
        nho[a[i]].emplace_back(b[i]);

    root[0] = build();
    for (int i = 1; i <= n; i++) {
        root[i] = root[i-1];
        for (int j : nho[i]) root[i] = upd(j, root[i]);
    }
}

void init(int N, int A[], int B[]) {
    n = N;
    for (int i = 0; i < N; i++) a[i] = A[i];
    for (int i = 0; i < N; i++) b[i] = B[i];
    preprocess();
}

void builderman(int k, node *cur, node *er, int lo = 1, int hi = n) {
    if (lo == hi) {
        er = cur;
        return;
    }
    int mid = (lo + hi) >> 1, trai = cur->left_child->val;
    if (k <= trai) {
        er->extend_left(); er->extend_right();
        builderman(k, cur->left_child, er->left_child, lo, mid);
    }
    else {
        er->left_child = cur->left_child; er->extend_right();
        builderman(k-trai, cur->right_child, er->right_child, mid+1, hi);
    }

    er->val = er->left_child->val + er->right_child->val;
}

int prefix_sum = 0;

int solve(int u) {
    if (root[u]->val - er->val < u) return 0;
    builderman(prefix_sum+u, root[u], er);
    return 1;
}

int can(int M, int K[]) {
    sort(K, K + M);
    er = new node();
    for (int i = 0; i < M; i++) {
        if (K[i] > n) return 0;
        if (!solve(K[i])) return 0;
        prefix_sum += K[i];
    }
    return 1;
}

/*
4
1 2
2 3
2 3
2 4
2
2 1 3
2 1 1
*/

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