Submission #71338

#	Time	Username	Problem	Language	Result	Execution time	Memory
71338		fallingstar	Teams (IOI15_teams)	C++14	77 / 100	4101 ms	492740 KiB

teams

#include "teams.h"
#include <cstring>
#include <algorithm>
#include <vector>
#include <deque>
#include <numeric>

using namespace std;

const int N = 5e5 + 2;
const int TREE_SIZE = 2e7;
const int MAGIC = 300;

int n;

struct TPersistentSegmentTree
{
	#define mid (sl + sr) / 2

	int cntVer = 0;
	struct TNode 
	{
		int sum = 0;
		TNode *lc = nullptr, *rc = nullptr;
	} *root[N], *cache = new TNode[TREE_SIZE], *it = cache;

	inline int GetSum(TNode *node) { return node ? node->sum : 0; }
	inline TNode* GetLeft(TNode *node) { return node ? node->lc : nullptr; }
	inline TNode* GetRight(TNode *node) { return node ? node->rc : nullptr; }

	TNode* Update(TNode *cur, int sl, int sr, int u)
	{
		TNode *node = it++;
		node->sum = GetSum(cur) + 1;
		if (sl < sr)
			if (u <= mid)
			{
				node->lc = Update(GetLeft(cur), sl, mid, u);
				node->rc = GetRight(cur);
			}
			else
			{
				node->lc = GetLeft(cur);
				node->rc = Update(GetRight(cur), mid + 1, sr, u);
			}
		return node;
	}
	int Query(TNode *node, int sl, int sr, int ql, int qr)
	{
		if (!node || qr < sl || sr < ql) return 0;
		if (ql <= sl && sr <= qr) return node->sum;
		return Query(node->lc, sl, mid, ql, qr) + Query(node->rc, mid + 1, sr, ql, qr);
	}

	int Update(int ver, int u) { root[++cntVer] = Update(root[ver], 1, n, u); return cntVer; }
	int Query(int ver, int l, int r) { return Query(root[ver], 1, n, l, r); }
	#undef mid
} segtree;

int verId[N];
pair<int, int> segs[N];

void init(int _n, int A[], int B[]) 
{
	n = _n;
	vector<int> vals(n);
	for (int i = 0; i < n; ++i) vals[i] = i;
	sort(vals.begin(), vals.end(), [&](int lhs, int rhs) { return A[lhs] < A[rhs]; });
	auto it = vals.begin();
	for (int i = 1; i <= n; ++i)
	{
		verId[i] = verId[i - 1];
		while (it != vals.end() && A[*it] <= i)
		{
			verId[i] = segtree.Update(verId[i], B[*it]);
			++it;
		}
	}

	for (int i = 0; i < n; ++i) segs[i] = make_pair(A[i], B[i]);
	sort(segs, segs + n, [](pair<int, int> lhs, pair<int, int> rhs) { return lhs.second < rhs.second; });
}

int nex[N];
int cnt[N];
int GetNext(int x) { return nex[x] == x ? cnt[x] ? x : nex[x] = GetNext(x + 1) : nex[x] = GetNext(nex[x]); }

int SolveN(int M, int K[])
{
	memset(nex, -1, sizeof(nex));
	memset(cnt, 0, sizeof(cnt));
	for (int i = 0; i < M; ++i) nex[K[i]] = K[i], cnt[K[i]] += K[i];
	nex[n + 1] = cnt[n + 1] = n + 1;
	for (int i = n; i >= 1; --i)
		if (nex[i] == -1) nex[i] = nex[i + 1];
	for (int i = 1, j = 0; i <= n; ++i)
	{
		while (j < n && segs[j].second == i)
		{
			int proj = GetNext(segs[j].first);
			if (proj <= i) --cnt[proj];
			++j;
		}
	}
	return GetNext(1) == n + 1;
}

int can(int M, int K[]) 
{
	if (accumulate(K, K + M, 0LL) > n) return 0;

	if (M >= MAGIC) return SolveN(M, K);

	sort(K, K + M);

	deque<pair<int, int> > pend;

	for (int i = 0, j = 0; i < M; i = j)
	{
		while (j < M && K[j] == K[i]) ++j;
		pend.push_back(make_pair(K[i], K[i] * (j - i)));
		int nextK = (j < M ? K[j] - 1 : n);

		int lastSum = 0;
		int students = 0;

		for (auto it = pend.begin(); it != pend.end(); )
		{
			int curQuery = it->first;
			int curSum = segtree.Query(verId[curQuery], K[i], nextK);

			students += curSum - lastSum;
			int dec = min(students, it->second);
			if (dec == it->second)
			{
				it = pend.erase(it);
			}	
			else
			{
				it->second -= dec;
				++it;
			}
			students -= dec;
			lastSum = curSum;
		}
	}
	return pend.empty();
}

Compilation message (stderr)

teams.cpp: In member function 'TPersistentSegmentTree::TNode* TPersistentSegmentTree::Update(TPersistentSegmentTree::TNode*, int, int, int)':
teams.cpp:35:6: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   if (sl < sr)
      ^

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