Submission #589323

#	Time	Username	Problem	Language	Result	Execution time	Memory
589323		Temmie	Teams (IOI15_teams)	C++17	100 / 100	2566 ms	215876 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>

struct Seg {
	
	struct Item {
		int val = 0, l = 0, r = 0;
	};
	
	int size;
	std::vector <Item> v;
	
	Seg() : size(1), v(1, Item()) { }
	
	int update(int ind, int now, int l, int r) {
		int nv = size++;
		v.push_back(Item());
		v[nv].val = v[now].val;
		if (!(r - l - 1)) {
			v[nv].val++;
			return nv;
		}
		if (!v[now].l) {
			v[now].l = size++;
			v[now].r = size++;
			v.resize(v.size() + 2, Item());
		}
		v[nv].l = v[now].l;
		v[nv].r = v[now].r;
		int mid = (l + r) >> 1;
		if (ind < mid) {
			int j = update(ind, v[now].l, l, mid);
			v[nv].l = j;
		} else {
			int j = update(ind, v[now].r, mid, r);
			v[nv].r = j;
		}
		v[nv].val = v[v[nv].l].val + v[v[nv].r].val;
		return nv;
	}
	
	int query(int tl, int tr, int now, int l, int r) {
		if (l >= tr || r <= tl) {
			return 0;
		}
		if (l >= tl && r <= tr) {
			return v[now].val;
		}
		int mid = (l + r) >> 1;
		return
		(v[now].l ? query(tl, tr, v[now].l, l, mid) : 0)
		+
		(v[now].r ? query(tl, tr, v[now].r, mid, r) : 0);
	}
	
};

int n;
std::vector <std::pair <int, int>> a;
std::vector <int> ord, rt;
Seg seg;

void init(int N, int A[], int B[]) {
	n = N;
	a.resize(n);
	for (int i = 0; i < n; i++) {
		a[i] = { A[i], B[i] };
	}
	ord.resize(n);
	std::iota(ord.begin(), ord.end(), 0);
	std::sort(ord.begin(), ord.end(), [] (int u, int v) -> bool { return a[u] < a[v]; });
	rt.resize(n + 1, 0);
	for (int i = 1, cnt = 0; i <= n; i++) {
		rt[i] = rt[i - 1];
		while (cnt < n && i >= a[ord[cnt]].first) {
			rt[i] = seg.update(a[ord[cnt]].second, rt[i], 1, n + 1);
			cnt++;
		}
	}
}

int can(int m, int k[]) {
	std::sort(k, k + m);
	long long sum = 0;
	for (int i = 0; i < m; i++) {
		sum += k[i];
	}
	if (sum > n) {
		return false;
	}
	std::vector <std::pair <int, int>> now;
	for (int cnt, i = 0; i < m; i++) {
		cnt = i;
		for (; cnt + 1 < m && k[cnt + 1] == k[cnt]; cnt++);
		int num = cnt - i + 1;
		now.emplace_back(k[i], k[i] * num);
		i = cnt;
	}
	now.emplace_back(n + 1, 0);
	std::vector <int> running(now.size(), 0);
	for (int i = 0; i < (int) now.size(); i++) {
		int cnt = now[i].second;
		for (int j = i; j < (int) now.size() && cnt; j++) {
			int x;
			int mn = std::min(
			x = seg.query(now[j].first, now[j + 1].first, rt[now[i].first], 1, n + 1) - running[j], cnt);
			running[j] += mn;
			cnt -= mn;
		}
		if (cnt) {
			return false;
		}
	}
	return true;
}

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