Submission #287150

#	Time	Username	Problem	Language	Result	Execution time	Memory
287150		Saboon	Teams (IOI15_teams)	C++14	34 / 100	4127 ms	407544 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 5e5 + 10;
const int SQRT = 1000;

int n;
map<int,int> fen[maxn];

void add(int x, int y){
	for (int idx = x; idx < maxn; idx += idx & -idx)
		for (int idy = y; idy < maxn; idy += idy & -idy)
			fen[idx][idy] ++;
}

int get(int x, int y){
	int ret = 0;
	for (; x; x -= x & -x)
		for (int idy = y; idy; idy -= idy & -idy)
			ret += fen[x][idy];
	return ret;
}

int get(int x, int l, int r){
	return get(x, r) - get(x, l-1);
}

void init(int N, int A[], int B[]){
	n = N;
	for (int i = 0; i < n; i++)
		add(A[i],B[i]);
}

int up[SQRT], bup[SQRT];

int can(int m, int k[]){
	sort(k,k+m);
	int idx = 0, cnt = 0;
	for (int i = 0; i < m; i++){
		cnt ++;
		if (i == m-1 or k[i] != k[i+1]){
			if (1LL*cnt*k[i] > n)
				return false;
			up[idx] = k[i], bup[idx] = cnt*k[i];
			cnt = 0, idx++;
			continue;
		}
	}
	int CommonUse = 0;
	up[idx] = n+1;
	for (int i = 0; i < idx; i++){
		int me = get(up[i], up[i], up[i+1]-1);
		int LastUse = 0;
		if (i > 0)
			LastUse = get(up[i-1], up[i], up[i+1]-1);
		LastUse = min(CommonUse, LastUse);
		CommonUse -= LastUse;
		me -= LastUse;
		bup[i] -= me;
		if (bup[i] > 0){
			int T = get(up[i], up[i+1], n);
			T -= CommonUse;
			if (T < bup[i])
				return false;
			CommonUse += bup[i];
		}
	}
	return true;
}

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