Submission #1150428

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150428		Pekiban	Teams (IOI15_teams)	C++20	34 / 100	4091 ms	257856 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")

using namespace std;
#define pb push_back

const int N = 2e7+5;
int lc[N], rc[N], st[N], Ro[N], Cn, n;
int build(int l2 = 1, int r2 = n) {
	if (l2 == r2)	return ++Cn;
	int m2 = (l2 + r2)/2, nd = ++Cn;
	lc[nd] = build(l2, m2), rc[nd] = build(m2+1, r2);
	return nd;
}
int I = 0;
int upd(int nd, vector<int> &f, int l2 = 1, int r2 = n) {
	if (l2 == r2) {
		int ND = ++Cn; st[ND] = st[nd];
		while (I < (int)f.size() && f[I] == l2)	st[ND]++, I++;
		return ND;
	}
	int m2 = (l2 + r2)/2, ND = ++Cn;
	if (I < (int)f.size() && f[I] <= m2)	lc[ND] = upd(lc[nd], f, l2, m2);
	else
		lc[ND] = lc[nd];
	if (I < (int)f.size())	rc[ND] = upd(rc[nd], f, m2+1, r2);
	else
		rc[ND] = rc[nd];
	st[ND] = st[lc[ND]] + st[rc[ND]];
	return ND;
}
int sum(int l, int r, int nd, int l2 = 1, int r2 = n) {
	if (l <= l2 && r2 <= r)	return st[nd];
	int m2 = (l2 + r2)/2, S = 0;
	if (l <= m2)	S += sum(l, r, lc[nd], l2, m2);
	if (m2+1 <= r)	S += sum(l, r, rc[nd], m2+1, r2);
	return S;
}
int sum(int l, int r) {
	if (r < l)	return 0;
	return sum(l, r, Ro[r]);
}
int summ(int l, int r, int nb) {
	if (r < l)	return 0;
	return sum(l, r, nb);
}
void init(int NN, int A[], int B[]) {
	n = NN;
	Ro[0] = build();
	vector<int> a[n+1];
	for (int i = 0; i < n; ++i)	a[B[i]].pb(A[i]);
	for (int i = 0; i < n; ++i)	{
		I = 0;
		sort(a[i+1].begin(), a[i+1].end());
		Ro[i+1] = upd(Ro[i], a[i+1]);
	}
}
int can(int M, int K[]) {
	vector<pair<int, int>> v = {{0, 0}};
	long long S = 0;
	sort(K, K+M);
	for (int i = 0; i < M; ++i) {
		long long j = i;
		while (i+1 < M && K[i] == K[i+1])	++i;
		v.pb({K[i], (int)(i - j + 1)});
		S += K[i] * (i - j + 1);
	}
	if (S > n)	return 0;
	int dp[v.size()];
	dp[0] = 0;
	vector<pair<int, int>> op = {{0, n+1}};
	for (int i = 1; i < (int)v.size(); ++i) {
		while (op.back().second <= v[i].first)	op.pop_back();
		int p = op.back().first;
		dp[i] = dp[p] + sum(v[p].first+1, v[i].first-1) + v[i].first * v[i].second;
		if (dp[i] + sum(v[i].first+1, n) > n)	return 0;
		int mn = n+1;
		for (int j = 0; j < (int)op.size(); ++j) {
			int L = v[i].first+1, R = n, t = n+1;
			while (L <= R) {
				int m = (L + R)/2;
				if (dp[op[j].first] - dp[i] >= -summ(v[op[j].first].first+1, v[i].first, Ro[m-1]))
					R = m-1, t = m;
				else
					L = m+1;
			}
			mn = min(mn, t);
		}
		op.pb({i, mn});
	}
	return 1;
}

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