Submission #292549

#	Time	Username	Problem	Language	Result	Execution time	Memory
292549		Monochromatic	팀들 (IOI15_teams)	C++17	77 / 100	4073 ms	159096 KiB

teams

#include "teams.h"
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

int n;
vector<int> sweep[500005];

int rt[500005], lf[20 * 500005], rg[20 * 500005], sum[20 * 500005], sz;

void upd(int bf, int &nd, int cl, int cr, int v){
	nd = ++ sz;
	lf[nd] = lf[bf]; rg[nd] = rg[bf]; sum[nd] = sum[bf] + 1;
	if(cl == cr) return;

	if(v <= (cl + cr) / 2)
		upd(lf[bf], lf[nd], cl, (cl + cr) / 2, v);
	else
		upd(rg[bf], rg[nd], (cl + cr) / 2 + 1, cr, v);
}

int que(int nd, int cl, int cr, int ql, int qr){
	if(qr < cl || cr < ql || cl > cr) return 0;
	if(ql <= cl && cr <= qr) return sum[nd];
	return que(lf[nd], cl, (cl + cr) / 2, ql, qr) + que(rg[nd], (cl + cr) / 2 + 1, cr, ql, qr);
}

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

	for(int i = 1; i <= n; i ++){
		rt[i] = rt[i - 1];
		for(int x : sweep[i])
			upd(rt[i], rt[i], 1, n, x);
	}
}

int val[500005], cnt[500005], used[500005];
int can(int M, int K[]){
	// (N + M) log N
	// vector<int> cnt(n + 1, 0);
	// for(int i = 0; i < M; i ++)
	// 	cnt[K[i]] += K[i];

	// priority_queue<int, vector<int>, greater<int> > pq;
	// for(int i = 1; i <= n; i ++){
	// 	for(int x : sweep[i]) pq.push(x);
	// 	while(pq.size() && pq.top() < i) pq.pop();
	// 	if(pq.size() < cnt[i]) return 0;
	// 	for(; cnt[i] --; pq.pop());
	// }
	// return 1;

	// M^2 log N
	sort(K, K + M);
	int sum = 0, id = 0;
	for(int i = 0; i < M; i ++){
		sum += K[i];
		if(id > 0 && val[id - 1] == K[i])
			cnt[id - 1] += K[i];
		else
			val[id] = cnt[id] = K[i], id ++;
	}
	val[id] = n + 1;

	if(sum > n) return 0;
	for(int i = 0; i < id; i ++)
		used[i] = 0;

	for(int i = 0; i < id; i ++){
		int need = cnt[i];
		for(int j = i; j < id; j ++){
			int have = que(rt[val[i]], 1, n, val[j], val[j + 1] - 1) - used[j];
			int add = min(have, need);
			need -= add; used[j] += add;
			if(need <= 0) break;
		}
		if(need > 0) return 0;
	}

	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:59:6: warning: declaration of 'sum' shadows a global declaration [-Wshadow]
   59 |  int sum = 0, id = 0;
      |      ^~~
teams.cpp:10:51: note: shadowed declaration is here
   10 | int rt[500005], lf[20 * 500005], rg[20 * 500005], sum[20 * 500005], sz;
      |                                                   ^~~

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