Submission #48074

#	Time	Username	Problem	Language	Result	Execution time	Memory
48074		cheater2k	Teams (IOI15_teams)	C++17	34 / 100	4056 ms	430776 KiB

teams

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

const int N = 500005;

int n;
int cntRig[N];
vector <int> lef[N];
int ver[N];

#define mid ((l + r) >> 1)
struct PersistentIT {
	int T[N * 30], L[N * 30], R[N * 30], peak;

	int build(int l, int r) {
		if (l == r) {
			++peak; L[peak] = R[peak] = peak; return peak;
		}
		int u = ++peak;
		L[u] = build(l, mid);
		R[u] = build(mid + 1, r);
		return u;
	}	
	
	int upd(int v, int l, int r, int x, int val) { // a[x] += val
		if (r < x || l > x) return v;
		if (l == r) {
			++peak; T[peak] = T[v] + val; L[peak] = R[peak] = peak; return peak;
		}
		int u = ++peak;
		L[u] = upd(L[v], l, mid, x, val);
		R[u] = upd(R[v], mid + 1, r, x, val);
		T[u] = T[L[u]] + T[R[u]];
		//printf("u = %d l = %d r = %d -> leftchild = %d rightchild = %d => T = %d\n", u, l, r, L[u], R[u], T[u]);
		return u;
	}
} pit;

struct IT {
	int T[N << 2];
	vector < pair<int,int> > buf; // history

	void upd(int v, int l, int r, int x, int val) {
		if (r < x || l > x) return;
		if (l == r) { if (val > 0) buf.push_back(make_pair(x, val)); T[v] += val; return; }
		upd(v << 1, l, mid, x, val);
		upd(v << 1 | 1, mid + 1, r, x, val);
		T[v] = T[v << 1] + T[v << 1 | 1];
	}

	void reset() {
		while(buf.size()) {
			auto i = buf.back(); buf.pop_back();
			upd(1, 1, n, i.first, -i.second);
		}
	}
} it;

// --------------------------------

void init(int _n, int A[], int B[]) {
	n = _n;
	for (int i = 0; i < n; ++i) {
		cntRig[B[i]]++;
		lef[A[i]].push_back(B[i]);
	}
	pit.build(1, n);
	ver[0] = 1;
	for (int i = 1; i <= n; ++i) {
		ver[i] = ver[i - 1];
		if (cntRig[i - 1]) {
			ver[i] = pit.upd(ver[i], 1, n, i - 1, -cntRig[i - 1]); // delete
		}
		for (auto &j : lef[i]) {
			ver[i] = pit.upd(ver[i], 1, n, j, +1); // add
		}
	}
}

int find(int pv, int v, int l, int r, int leftmost) { 
	// pv is the index in PIT, v is the index in IT
	// find the smallest i >= leftmost such that pit[i] - it[i] > 0
	if (r < leftmost) return 0;
	if (l >= leftmost) {
		if (l == r) {
			if (pit.T[pv] > it.T[v]) return l; 
			else return 0;
		}
		if (pit.T[pv] <= it.T[v]) return 0;
	}
	int ret = find(pit.L[pv], v << 1, l, mid, leftmost);
	if (!ret) return find(pit.R[pv], v << 1 | 1, mid + 1, r, leftmost);
	else return ret;
}

int can(int m, int sz[]) {
	sort(sz, sz + m);
	for (int i = 0; i < m; ++i) {
		int s = sz[i];
		while(sz[i]--) {
			int pos = find(ver[s], 1, 1, n, s);
			if (pos == 0) {
				it.reset();
				return false;
			}
			it.upd(1, 1, n, pos, +1);
		}
	}

	it.reset();
	return true;
}

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