Submission #828503

#	Time	Username	Problem	Language	Result	Execution time	Memory
828503		Josia	Teams (IOI15_teams)	C++17	77 / 100	4074 ms	449212 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;

	vector<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.resize(n);
		
		for (int i = 0; i<(int)n; i++) {
			assert(i == rangesWithSortedIndicies[i].first.second);
			startTimes[i] = tree.update(i == 0 ? 0 : 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(indexBeginL == 0 ? 0 : startTimes[indexBeginL-1], 0, n-1, indexEndL, indexEndR);
		return right-left;
	}
};

vector<int> allBeginR, allEndL;

Query queryEngine;

void makeAll() {
	allBeginR.assign(n+1, -1);
	allEndL.assign(n+1, -1);
	for (int i = 1; i<=n; i++) {
		auto pBeginR = lower_bound(queryEngine.beginWithIndicies.begin(), queryEngine.beginWithIndicies.end(), pair<int, int>{i, 1e9});
		auto pEndL = lower_bound(queryEngine.endWithIndicies.begin(), queryEngine.endWithIndicies.end(), pair<int, int>{i-1, 1e9});

		if (pBeginR != queryEngine.beginWithIndicies.begin()) allBeginR[i] = (*prev(pBeginR)).second;
		if (pEndL != queryEngine.endWithIndicies.end()) allEndL[i] = (*pEndL).second;		
	}
}


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






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) {
		int groupsize = i.first;
		int people = i.first * i.second;


		int cnt = 0;

		int beginR = allBeginR[groupsize], endL = allEndL[groupsize];

		if (beginR == -1 || endL == -1) {return 0;}

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

			if (cnt+add >= people) break;

			cnt += add;

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

			s.pop_back();

			if (s.empty()) return 0;

		}

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

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

	return 1;
}

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