제출 #1222015

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1222015		HappyCapybara	팀들 (IOI15_teams)	C++20	77 / 100	818 ms	544336 KiB

teams

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

int n;

struct node {
	node *lc, *rc;
	int val, tl, tr;

	node(node* lcc, node* rcc, int v, int tll, int trr){
		lc = lcc;
		rc = rcc;
		val = v;
		tl = tll;
		tr = trr;
	}
};

vector<node*> roots;

void build(node* cur){
	if (cur->tl == cur->tr) return;
	int tm = (cur->tl+cur->tr)/2;
	cur->lc = new node(nullptr, nullptr, 0, cur->tl, tm);
	cur->rc = new node(nullptr, nullptr, 0, tm+1, cur->tr);
	build(cur->lc);
	build(cur->rc);
}

node* update(node* cur, int pos){
	if (cur->tl == cur->tr) return new node(nullptr, nullptr, cur->val+1, cur->tl, cur->tr);
	int tm = (cur->tl+cur->tr)/2;
	node* nn = new node(cur->lc, cur->rc, cur->val, cur->tl, cur->tr);
	if (pos <= tm) nn->lc = update(nn->lc, pos);
	else nn->rc = update(nn->rc, pos);
	nn->val = nn->lc->val+nn->rc->val;
    return nn;
}

int query(node* cur, int l, int r){
	if (l > r) return 0;
	if (r < cur->tl || cur->tr < l) return 0;
	if (l <= cur->tl && cur->tr <= r) return cur->val;
	int tm = (cur->tl+cur->tr)/2;
	int res = 0;
	if (l <= tm) res += query(cur->lc, l, r);
	if (tm+1 <= r) res += query(cur->rc, l, r);
	return res;
}

void init(int N, int A[], int B[]){
	n = N;
	roots.push_back(new node(nullptr, nullptr, 0, 1, N));
	build(roots.back());
	vector<vector<int>> ev(N+1);
	for (int i=0; i<N; i++) ev[A[i]].push_back(B[i]);
	for (int i=1; i<=N; i++){
		roots.push_back(roots.back());
		for (int x : ev[i]){
			node* nn = update(roots.back(), x);
			roots.pop_back();
			roots.push_back(nn);
		}
	}
	/*for (int i=1; i<=N; i++){
		for (int j=i; j<=N; j++) cout << query(roots[i], j, N) << " ";
		cout << endl;
	}*/
}

int can(int M, int K[]){
	sort(K, K+M);
	vector<int> ch;
	for (int i=0; i<M; i++){
		if (i == M-1 || K[i] != K[i+1]) ch.push_back(K[i]);
	}
	int q = ch.size();
	ch.push_back(n+1);
	vector<int> occ(q, 0);
	//cout << endl;
	for (int i=0; i<M; i++){
		//cout << K[i] << endl;
		int req = K[i];
		for (int j=0; j<q; j++){
			if (ch[j] < K[i]) continue;
			int rem = query(roots[K[i]], ch[j], ch[j+1]-1)-occ[j];
			//cout << rem << endl;
			if (rem > req){
				occ[j] += req;
				req = 0;
			}
			else {
				req -= rem;
				occ[j] += rem;
			}
			if (!req) break;
		}
		//cout << req << endl;
		if (req) return false;
	}
	return true;
}

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