제출 #292552

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
292552		Monochromatic	팀들 (IOI15_teams)	C++17	77 / 100	4099 ms	153208 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 block = 707; // sqrt(N)
int can(int M, int K[]){
	if(M > block){
		// (N + M) log N -> sqrt(N) * (N + sqrt(N)) log N = N * sqrt(N) * 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;
	}
	else{
		// M^2 log N -> sqrt(N) * (sqrt(N)) ^ 2 log N = N sqrt(N) 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;
	}

	return 69;
}

컴파일 시 표준 에러 (stderr) 메시지

teams.cpp: In function 'int can(int, int*)':
teams.cpp:46:19: warning: declaration of 'cnt' shadows a global declaration [-Wshadow]
   46 |   vector<int> cnt(n + 1, 0);
      |                   ^
teams.cpp:41:18: note: shadowed declaration is here
   41 | int val[500005], cnt[500005], used[500005];
      |                  ^~~
teams.cpp:54:17: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int, std::vector<int>, std::greater<int> >::size_type' {aka 'long unsigned int'} and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} [-Wsign-compare]
   54 |    if(pq.size() < cnt[i]) return 0;
teams.cpp:62:7: warning: declaration of 'sum' shadows a global declaration [-Wshadow]
   62 |   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