Submission #621207

#	Time	Username	Problem	Language	Result	Execution time	Memory
621207		yanndev	Teams (IOI15_teams)	C++17	13 / 100	736 ms	478620 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;

const int MX_N = 500042;

int n;
pair<int, int> stud[MX_N];
vector<int> startAt[MX_N];
int bit[MX_N];
int tree[2 * 32 * MX_N], lc[2 * 32 * MX_N], rc[2 * 32 * MX_N], roots[MX_N];
int nxtIdx = 2;

void add(int idx, int val) {
	for (++idx; idx < MX_N; idx += (idx & -idx))
		bit[idx] += val;
}

int getPref(int idx) {
	int ans = 0;
	for (++idx; idx > 0; idx -= (idx & -idx))
		ans += bit[idx];
	return ans;
}

int getSum(int l, int r) {
	return getPref(r) - getPref(l - 1);
}

void cpy(int& node) {
	lc[nxtIdx] = lc[node];
	rc[nxtIdx] = rc[node];
	tree[nxtIdx] = tree[node];
	node = nxtIdx++;
}

void upd(int& node, int cL, int cR, int qL, int qR, int val) {
	if (cL > qR || cR < qL)
		return;
	cpy(node); 
	if (qL <= cL && cR <= qR) {
		tree[node] += val;
		return;
	}

	int mid = (cL + cR) / 2;
	upd(lc[node], cL, mid, qL, qR, val);
	upd(rc[node], mid + 1, cR, qL, qR, val);	
	tree[node] = tree[lc[node]] + tree[rc[node]];
}

int getFirst(int node, int cL, int cR, int mnRight) {
	if (cR < mnRight || node == 0)
		return -1;

	assert(tree[node] >= getSum(cL, cR));
	if (tree[node] - getSum(cL, cR) <= 0)
		return -1;

	if (cL == cR)
		return cL;
	
	int mid = (cL + cR) / 2;
	int a = getFirst(lc[node], cL, mid, mnRight);
	if (a != -1)
		return a;
	return getFirst(rc[node], mid + 1, cR, mnRight);
}

void init(int N, int A[], int B[]) {
	memset(tree, 0, sizeof(tree));
	memset(bit, 0, sizeof(bit));
	
	for (int i = 0; i < N; i++) {
		stud[i] = {A[i], B[i]};
		startAt[A[i]].push_back(B[i]);
	}

	n = N;
	roots[0] = 1;
	for (int i = 1; i <= n; i++) {
		roots[i] = roots[i - 1];
		for (auto& x: startAt[i])
			upd(roots[i], 1, n, x, x, 1);
	}
}

int can(int M, int K[]) {
	sort(K, K + M);
	vector<int> toRem {};

	for (int i = 0; i < M; i++) {
		int req = K[i];

		while (req) {
			int id = getFirst(roots[K[i]], 1, n, K[i]);
			if (id == -1)
				break;

			toRem.push_back(id);
			add(id, 1);
			req--;
		}

		if (req != 0)
			return 0;
	}

	for (auto& x: toRem)
		add(x, -1);
	return 1;
}

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