Submission #1222011

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222011		HappyCapybara	Teams (IOI15_teams)	C++20	77 / 100	821 ms	526768 KiB

teams

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

int n;

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

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

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);
}

void update(node* cur, int pos){
	if (cur->tl == cur->tr){
		cur->val++;
		return;
	}
	int tm = (cur->tl+cur->tr)/2;
	if (pos <= tm){
		if (!cur->nl){
			cur->lc = new node(cur->lc->lc, cur->lc->rc, cur->lc->val, cur->lc->tl, cur->lc->tr);
			cur->nl = true;
		}
		update(cur->lc, pos);
	}
	else {
		if (!cur->nr){
			cur->rc = new node(cur->rc->lc, cur->rc->rc, cur->rc->val, cur->rc->tl, cur->rc->tr);
			cur->nr = true;
		}
		update(cur->rc, pos);
	}
	cur->val = cur->lc->val+cur->rc->val;
}

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(new node(roots.back()->lc, roots.back()->rc, roots.back()->val, roots.back()->tl, roots.back()->tr));
		for (int x : ev[i]) update(roots.back(), x);
	}
	/*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