Submission #432118

#	Time	Username	Problem	Language	Result	Execution time	Memory
432118		frodakcin	Teams (IOI15_teams)	C++11	0 / 100	151 ms	50916 KiB

teams

#include "teams.h"
#include <cassert>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <queue>
#include <vector>
#include <stack>
#include <functional>

template<typename T> bool ckmax(T& a, const T& b) {return b>a?a=b,1:0;}
template<typename T> bool ckmin(T& a, const T& b) {return b<a?a=b,1:0;}

using ll = long long;

const int MN = 5e5+10;
const int MQ = 2e5+10;

const int MX = 1e6 + 10;

int N, A[MN], B[MN], ord[MN];
int sv[MX], sl[MX], sr[MX], X, root[MN];

int nn(int p=0)
{
	++X;
	assert(X<MX);
	if(p!=0)
		sv[X]=sv[p], sl[X]=sl[p], sr[X]=sr[p];
	return X;
}

void upd(int &n, int l, int r, int q)
{
	n=nn(n);
	++sv[n];
	if(r-l>1)
	{
		int m=l+(r-l)/2;
		if(q<m) upd(sl[n], l, m, q);
		else upd(sr[n], m, r, q);
	}
}

int qry(int n, int l, int r, int ql, int qr)
{
	if(n==0) return 0;
	if(ql <= l&&r <= qr) return sv[n];
	else
	{
		int m=l+(r-l)/2, f=0;
		if(ql < m) f += qry(sl[n], l, m, ql, qr);
		if(m < qr) f += qry(sr[n], m, r, ql, qr);
		return f;
	}
}

int get(int l1, int l2, int r1, int r2) // (l1, l2], [r1, r2)
{
	if(r1>=r2) return 0;
	return qry(root[l2], 1, N+1, r1, r2)-qry(root[l1], 1, N+1, r1, r2);
}

int qry2(int u, int v, int l, int r, int ql, int q)// pos if answer, neg if fails to reach
{
	if(q==0) return l;
	if(ql <= l&&sv[v]-sv[u]<q) return sv[u]-sv[v];
	if(r-l>1)
	{
		int m=l+(r-l)/2, vl=0;
		if(ql < m) vl=qry2(sl[u], sl[v], l, m, ql, q);
		if(vl > 0) return vl;
		int ans = qry2(sr[u], sr[v], m, r, ql, q+vl);
		if(ans>0) return ans;
		return ans+vl;
	}
	else
		return r;
}

int find(int l1, int l2, int r1, int q)
{ // returns smallest r2, where get(l1, l2, r1, r2) >= q
	return qry2(root[l1], root[l2], 1, N+1, r1, q);
}

void init(int _N, int _A[], int _B[]) {
	N=_N;
	memcpy(A, _A, N*sizeof*_A);
	memcpy(B, _B, N*sizeof*_B);
	std::iota(ord, ord+N, 0);
	std::sort(ord, ord+N, [&](int u, int v){return A[u]<A[v];});

	for(int i=1, j=0;i<=N;++i)
	{
		root[i] = root[i-1];
		for(;j < N && A[ord[j]] == i;++j)
			upd(root[i], 1, N+1, B[ord[j]]);
	}
}

struct obj
{
	public:
		int l, r, spare; // (l, cur] x [cur, r) queried. Spare remain from [r-1, r)
};
int can(int M, int K[]) {
	std::sort(K, K+M);

	{
		ll sum=0;
		for(int i=0;i<M;++i) sum += K[i];
		if(sum > N) return 0;
	}

	std::vector<int> w;
	{
		int M2=0;
		for(int i=0;i<M;++i)
		{
			if(i==0||K[i]!=K[i-1])
				w.push_back(0), ++M2;
			w.back() += K[i];
			K[M2-1]=K[i];
		}
		M=M2;
	}

	std::stack<obj> stk;
	stk.push({0, N+1, 0});
	for(int i=0;i<M;++i)
	{
		int cur = K[i];
		int cur_L = cur;
		for(;;)
		{
			if(stk.empty()) return 0;
			if(ckmax(stk.top().r, cur)) stk.top().spare=0;
			int v = get(stk.top().l, cur, cur_L, stk.top().r-1);
			if(v < w[i])
			{
				int v2 = get(stk.top().l, cur, cur_L, stk.top().r);
				if(v2+stk.top().spare>=w[i])
				{
					stk.top().spare+=v2-w[i];
					stk.top().l = cur;
					break;
				}
				else
				{
					w[i] -= v2+stk.top().spare;
					cur_L = stk.top().r;
					stk.pop();
				}
			}
			else
			{
				int r = find(stk.top().l, cur, cur_L, w[i]);
				assert(cur_L <= r && r < stk.top().r);
				int v2 = get(stk.top().l, cur, cur_L, r);
				assert(v2 >= w[i]);
				stk.push({cur, r, v2-w[i]});
				break;
			}
		}
	}
	return 1;
}

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