Submission #71305

#	Time	Username	Problem	Language	Result	Execution time	Memory
71305		fallingstar	Teams (IOI15_teams)	C++14	77 / 100	4069 ms	485956 KiB

teams

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

using namespace std;

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

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];

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;
		}
	}
}

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

	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:33: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