Submission #828485

#	Time	Username	Problem	Language	Result	Execution time	Memory
828485		Josia	Teams (IOI15_teams)	C++17	77 / 100	4066 ms	469752 KiB

teams

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

using namespace std;

#define int int64_t

int n;

struct Query {
	struct seg {
		struct node {
			int val = 0;
			int l = -1;
			int r = -1;
		};
		vector<node> tree = {{0, -1, -1}};

		void build(int v, int rl, int rr) {
			if (rl == rr) return;

			tree[v].l = tree.size();
			tree.push_back(node());
			tree[v].r = tree.size();
			tree.push_back(node());

			int rm = (rl + rr)/2;
			build(tree[v].l, rl, rm);
			build(tree[v].r, rm+1, rr);
		}

		int update(int v, int rl, int rr, int pos, int val) {
			// cerr << v << "\n";
			if (rl == rr) {
				int newV = tree.size();

				tree.push_back(tree[v]);

				tree[newV].val = val;
				return newV;
			}
			int rm = (rl + rr)/2;

			int newV = tree.size();

			tree.push_back(tree[v]);

			if (pos <= rm) tree[newV].l = (update(tree[newV].l, rl, rm, pos, val));
			else tree[newV].r = (update(tree[newV].r, rm+1, rr, pos, val));

			tree[newV].val = tree[tree[newV].l].val + tree[tree[newV].r].val;

			return newV;
		}

		int query(int v, int rl, int rr, int ql, int qr) {
			if (ql > qr) return 0;

			if (rl == ql && rr == qr) return tree[v].val;

			int rm = (rl + rr)/2;

			return query(tree[v].l, rl, rm, ql, min(rm, qr)) + query(tree[v].r, rm+1, rr, max(rm+1, ql), qr);
		}
	};
	
	vector<pair<pair<int, int>, pair<int, int>>> rangesWithSortedIndicies;
	vector<pair<int, int>> beginWithIndicies;
	vector<pair<int, int>> endWithIndicies;

	unordered_map<int, int> startTimes;

	seg tree;

	void initQuery(vector<pair<int, int>> ranges) {
		rangesWithSortedIndicies.resize(n);
		beginWithIndicies.resize(n);
		endWithIndicies.resize(n);

		for (int i = 0; i<n; i++) {
			rangesWithSortedIndicies[i].first.first = ranges[i].first;
			rangesWithSortedIndicies[i].second.first = ranges[i].second;
		}

		sort(rangesWithSortedIndicies.begin(), rangesWithSortedIndicies.end());

		for (int i = 0; i<n; i++) {
			rangesWithSortedIndicies[i].first.second = i;
			swap(rangesWithSortedIndicies[i].first, rangesWithSortedIndicies[i].second);

			beginWithIndicies[i] = rangesWithSortedIndicies[i].second;
		}

		sort(rangesWithSortedIndicies.begin(), rangesWithSortedIndicies.end());

		for (int i = 0; i<n; i++) {
			rangesWithSortedIndicies[i].first.second = i;
			swap(rangesWithSortedIndicies[i].first, rangesWithSortedIndicies[i].second);

			endWithIndicies[i] = rangesWithSortedIndicies[i].second;
		}

		sort(rangesWithSortedIndicies.begin(), rangesWithSortedIndicies.end());

		assert(is_sorted(beginWithIndicies.begin(), beginWithIndicies.end()));
		assert(is_sorted(endWithIndicies.begin(), endWithIndicies.end()));

		// ----------- rangesWithSortedIndicies: {valBegin, indBegin}, {valEnd, indEnd}; sorted by begin. -----------

		tree.build(0, 0, n-1);

		startTimes[-1] = 0;
		
		for (int i = 0; i<(int)n; i++) {
			assert(i == rangesWithSortedIndicies[i].first.second);
			startTimes[i] = tree.update(startTimes[i-1], 0, n-1, rangesWithSortedIndicies[i].second.second, 1);
		}
	}


	int query(int indexBeginL, int indexBeginR, int indexEndL, int indexEndR) {
		int right = tree.query(startTimes[indexBeginR], 0, n-1, indexEndL, indexEndR);
		int left = tree.query(startTimes[indexBeginL-1], 0, n-1, indexEndL, indexEndR);
		return right-left;
	}
};


Query queryEngine;

void init(signed _N, signed A[], signed B[]) {
	n = _N;

	vector<pair<int, int>> ranges(n);

	for (int i = 0; i<n; i++) {
		ranges[i].first = A[i];
		ranges[i].second = B[i];
	}

	queryEngine.initQuery(ranges);
	
}

signed can(signed m, signed K[]) {
	map<int, int> projects;

	for (int i = 0; i<m; i++) {
		projects[K[i]]++;
	}

	vector<pair<int, int>> s;
	s.push_back({-1, n-1});

	for (pair<int, int> i: projects) {
		// for (auto j: s) cerr << j.first << " " << j.second << "; ";
		// cerr << "\n";

		int groupsize = i.first;
		int people = i.first * i.second;


		int cnt = 0;

		int beginR, endL;
		auto pBeginR = lower_bound(queryEngine.beginWithIndicies.begin(), queryEngine.beginWithIndicies.end(), pair<int, int>{groupsize, 1e9});
		auto pEndL = lower_bound(queryEngine.endWithIndicies.begin(), queryEngine.endWithIndicies.end(), pair<int, int>{groupsize-1, 1e9});

		if (pBeginR == queryEngine.beginWithIndicies.begin() || pEndL == queryEngine.endWithIndicies.end()) {return 0;}

		beginR = (*prev(pBeginR)).second;
		endL = (*pEndL).second;
		
		// cerr << beginR << " " << endL << "\n";

		// esay case: this group is out of the range
		while (s.back().second < endL) {
			s.pop_back();
			if (s.empty()) return 0;
		}


		while (true) {
			int add = queryEngine.query(s.back().first+1, beginR, endL, s.back().second);

			// cerr << cnt << " + " << add << "\n";

			if (cnt+add >= people) break;

			cnt += add;

			endL = s.back().second+1;

			s.pop_back();

			if (s.empty()) return 0;

		}

		// cerr << cnt << "\n";


		int beginL = s.back().first+1;
		

		int l = endL, r = s.back().second;

		while (l<r) {
			int mid = (l+r)/2;
			int res = queryEngine.query(beginL, beginR, endL, mid);

			if (res + cnt >= people) r = mid;
			else l = mid+1;
		}

		// cerr << queryEngine.query(beginL, beginR, endL, l) << "\n";

		s.push_back({beginR, l});
	}



	return 1;
}

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