Submission #1151351

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151351		Pekiban	Teams (IOI15_teams)	C++20	0 / 100	4094 ms	257836 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<array<int, 2>> 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;
	set<array<int, 2>> A, B;
	A.insert({0, n+1});
	B.insert({n+1, 0});
	auto f = [&](int i1, int i2) {
		int L = v[i1][0]+1, R = n, t = n+1;
		while (L <= R) {
			int m = (L + R)/2;
			if (dp[i1] - dp[i2] >= -summ(v[i1][0]+1, v[i2][0], Ro[m-1]))
				R = m-1, t = m;
			else
				L = m+1;
		}
		return t;
	};
	for (int i = 1; i < (int)v.size(); ++i) {
		while ((*B.begin())[0] <= i) {
			int X = (*B.begin())[0], Y = (*B.begin())[1];
			if (X != (*A.rbegin())[1]) {
				B.erase({X, Y});
				A.erase({Y, X});
				auto it = A.upper_bound({Y, X});
				int YY = (*it)[0], XX = (*it)[1];
				it--;
				A.erase({YY, XX});
				B.erase({XX, YY});
				int tm = f((*it)[0], YY);
				A.insert({YY, tm});
				B.insert({tm, YY});
			}
		}
		int p = (*A.rbegin())[0];
		dp[i] = dp[p] + sum(v[p][0]+1, v[i][0]-1) + v[i][0] * v[i][1];
		if (dp[i] + sum(v[i][0]+1, n) > n)	return 0;
		int tm = f((*A.rbegin())[0], i);
		A.insert({i, tm});
		B.insert({tm, i});
	}
	return 1;
}

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