Submission #1137299

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137299		alterio	Teams (IOI15_teams)	C++20	0 / 100	4102 ms	207348 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>

using namespace std;

const int mxn = 5e5 + 100;

int N;

vector<pair<int, int>> A;

struct Node {
	int sz, mnA, mxB, lz;
	vector<pair<int, int>> A;
};

struct SGT {
	vector<Node> sgt;

	SGT(int sz) {
		sgt.resize(4 * sz);
	}

	Node merge(Node a, Node b) {
		Node ans;
		ans.sz = {a.sz + b.sz};
		vector<pair<int, int>> v;
		for (auto x : a.A) v.push_back(x);
		for (auto x : b.A) v.push_back(x);
		sort(v.begin(), v.end());
		ans.A = v;
		ans.mnA = min(a.mnA, b.mnA);
		ans.mxB = max(a.mxB, b.mxB);
		return ans;
	}

	void build(int k, int l, int r) {
		if (l == r) {
			sgt[k].sz = 1;
			sgt[k].A.push_back({A[l].first, 1});
			sgt[k].mnA = A[l].first;
			sgt[k].mxB = A[l].second;
			return;
		}
		int mid = (l + r) / 2;
		build(k * 2, l, mid);
		build(k * 2 + 1, mid + 1, r);
		sgt[k] = merge(sgt[k * 2], sgt[k * 2 + 1]);
	}

	void push(int k, int l, int r) {
		if (sgt[k].lz == 1) {
			sgt[k * 2].lz = sgt[k * 2 + 1].lz = 1;
			for (auto x : sgt[k].A) x.second = 1;
			sgt[k].sz = r - l + 1;
		}
		if (sgt[k].lz == -1) {
			sgt[k * 2].lz = sgt[k * 2 + 1].lz = -1;
			for (auto x : sgt[k].A) x.second = 0;
			sgt[k].sz = 0;
		}
		sgt[k].lz = 0;
	}

	int get(int k, int l, int r, int i, int sz) {
		push(k, l, r);
		if (sgt[k].mnA > i || sgt[k].mxB < i || !sgt[k].sz) return 0;
		int mid = (l + r) / 2;
		if (sgt[k].mnA <= i && sgt[k].mxB >= i) {
			if (sgt[k].sz <= sz && sgt[k].sz == r - l + 1) {
				int SZ = sgt[k].sz;
				sgt[k].lz = -1;
				push(k, l, r);
				return SZ;
			}
			int ans = get(k * 2 + 1, mid + 1, r, i, sz);
			sgt[k] = merge(sgt[k * 2], sgt[k * 2 + 1]);
			if (ans == sz) return ans;
			ans += get(k * 2, l, mid, i, sz - ans);
			sgt[k] = merge(sgt[k * 2], sgt[k * 2 + 1]);
			return ans;
		}
		int ans = get(k * 2, l, mid, i, sz);
		if (ans != sz) ans += get(k * 2 + 1, mid + 1, r, i, sz - ans);
		sgt[k] = merge(sgt[k * 2], sgt[k * 2 + 1]);
		return ans;
	}
} sgt(mxn);

void init(int _N, int _A[], int _B[]) {
	N = _N;
	for (int i = 0; i < N; i++) A.push_back({_A[i], _B[i]});
	sort(A.begin(), A.end(), [&] (pair<int, int> a, pair<int, int> b) {
		return a.second < b.second;
	});
	sgt.build(1, 0, N - 1);
}

int can(int M, int K[]) {
	vector<int> v;
	for (int i = 0; i < M; i++) v.push_back(K[i]);
	sort(v.begin(), v.end());
	sgt.sgt[1].lz = 1;
	for (int i = 0; i < M; i++) {
		int people = sgt.get(1, 0, N - 1, v[i], v[i]);
		if (people != v[i]) return 0;
	}
	return 1;
}

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