Submission #97429

#	Time	Username	Problem	Language	Result	Execution time	Memory
97429		tincamatei	Teams (IOI15_teams)	C++14	100 / 100	3390 ms	380184 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX_N = 500000;
const int NNODES = 15000000;

struct AintPersistent {
	AintPersistent *sl, *sr;
	int val;
	AintPersistent() {
		val = 0;
		sl = sr = NULL;
	}
} cache[NNODES];
int topcache;

vector<AintPersistent*> root;

AintPersistent* mynew() {
	return &cache[topcache++];
}

AintPersistent* init(int l = 1, int r = MAX_N) {
	AintPersistent *rez = mynew();
	if(l < r) {
		int mid = (l + r) / 2;
		rez->sl = init(l, mid);
		rez->sr = init(mid + 1, r);
	}
	return rez;
}
 
AintPersistent* updateDfs(int poz, int val, int l, int r, AintPersistent* T) {
	if(r < poz || poz < l) return T;
	if(l == r) {
		AintPersistent* rez = mynew();
		rez->val = T->val + val;
		return rez;
	} else if(l < r) {
		int mid = (l + r) / 2;
		AintPersistent* rez = mynew();
		rez->sl = updateDfs(poz, val, l, mid, T->sl);
		rez->sr = updateDfs(poz, val, mid + 1, r, T->sr);
		rez->val = rez->sl->val + rez->sr->val;
		return rez;
	}
	return T;
}
 
int queryDfs(int i, int j, int l, int r, AintPersistent* T) {
	if(j < l || r < i || j < i) return 0;
	if(i <= l && r <= j)
		return T->val;
	else {
		int mid = (l + r) / 2;
		return queryDfs(i, j, l, mid, T->sl) +
					 queryDfs(i, j, mid + 1, r, T->sr);
	}
}
 
void update(int timestamp, int poz, int val) {
	root.push_back(updateDfs(poz, val, 1, MAX_N, root[timestamp]));
}
 
int query(int timestamp, int i, int j) {
	return queryDfs(i, j, 1, MAX_N, root[timestamp]);
}
 
pair<int, int> points[MAX_N];
int atable[1+MAX_N], btable[1+MAX_N];
 
// de jos in sus
bool bsort(pair<int, int> a, pair<int, int> b) {
	return a.second < b.second;
}
 
// de la stanga la dreapta
bool asort(pair<int, int> a, pair<int, int> b) {
	return a.first < b.first;
}

int N;
 
int getRealA(int A) {
	int st = -1, dr = N;
	while(dr - st > 1) {
		int mid = (st + dr) / 2;
		if(atable[mid] <= A)
			st = mid;
		else
			dr = mid;
	}
	return st + 1;
}
 
int getRealB(int B) {
	int st = -1, dr = N;
	while(dr - st > 1) {
		int mid = (st + dr) / 2;
		if(btable[mid] <= B)
			st = mid;
		else
			dr = mid;
	}
	return st + 1;
}

int query(int a1, int b1, int a2, int b2) {
	return query(a2, b1, b2) - query(a1 - 1, b1, b2);
}

int binsrc(AintPersistent* plusTree, AintPersistent* minusTree, int val, int l, int r) {
	if(l == r) return l;

	int mid = (l + r) / 2;
	int lval = plusTree->sl->val - minusTree->sl->val;
	if(lval >= val)
		return binsrc(plusTree->sl, minusTree->sl, val, l, mid);
	else
		return binsrc(plusTree->sr, minusTree->sr, val - lval, mid + 1, r);
}

void init(int _N, int A[], int B[]) {
	N = _N;
	
	root.push_back(init());
	for(int i = 0; i < N; ++i)
		points[i] = make_pair(A[i], B[i]);
	
	sort(points, points + N, bsort);
	for(int i = 0; i < N; ++i) {
		btable[i] = points[i].second;
		points[i].second = i + 1;
	}
	
	sort(points, points + N, asort);
	for(int i = 0; i < N; ++i) {
		atable[i] = points[i].first;
		points[i].first = i + 1;
	}
	
	for(int i = 0; i < N; ++i)
		update(i, points[i].second, 1);
}

vector<pair<int, int> > corners;

int can(int M, int K[]) {
	sort(K, K + M);
	corners.clear();
	corners.push_back(make_pair(0, MAX_N));
	for(int i = 0; i < M; ++i) {
		int ak = getRealA(K[i]),
		    bk = getRealB(K[i] - 1);

		while(!corners.empty() && corners.back().second <= bk)
			corners.pop_back();
		while(!corners.empty() && K[i] > 0) {
			int x = query(corners.back().first + 1, bk + 1, ak, corners.back().second);
			if(x <= K[i]) {
				K[i] -= x;
				bk = corners.back().second;
				corners.pop_back();
			} else {
				int cut = query(corners.back().first + 1, 1, ak, bk);
				bk = binsrc(root[ak], root[corners.back().first], cut + K[i], 1, MAX_N);
				K[i] -= query(corners.back().first + 1, 1, ak, bk) - cut;
			}
		}

		corners.push_back(make_pair(ak, bk));
		if(K[i] > 0)
			return false;
	}
	return true;
}

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