Submission #1163959

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163959		xnqs	Teams (IOI15_teams)	C++20	100 / 100	3103 ms	63900 KiB

teams

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <random>
#include <map>

#include "teams.h"

const int BLK_SIZE = 300;

int x;
std::vector<std::pair<int,int>> segments;
std::vector<int> tree[500005];
int fnwk[500005];

void tree_insert(int pos, int val) {
	while (pos <= x) {
		tree[pos].emplace_back(val);
		pos += pos&-pos;
	}
}

void tree_sort() {
	for (int i = 1; i <= x; i++) {
		std::sort(tree[i].begin(),tree[i].end());
	}
}

int tree_query(int pos, int l, int r) {
	int ret = 0;
	while (pos > 0) {
		ret += std::upper_bound(tree[pos].begin(),tree[pos].end(),r) - std::lower_bound(tree[pos].begin(),tree[pos].end(),l);
		pos ^= pos&-pos;
	}
	return ret;
}

void fnwk_add(int pos, int val) {
	while (pos <= x) {
		fnwk[pos] += val;
		pos += pos&-pos;
	}
}

int fnwk_query(int pos) {
	int ret = 0;
	while (pos > 0) {
		ret += fnwk[pos];
		pos ^= pos&-pos;
	}
	return ret;
}

void init(int N, int A[], int B[]) {
	x = N;

	for (int i = 0; i < x; i++) {
		tree_insert(A[i],B[i]);
		segments.emplace_back(A[i], B[i]);
	}

	std::sort(segments.begin(),segments.end(),[](const std::pair<int,int>& a, const std::pair<int,int>& b) {
		return a.first < b.first;
	});

	tree_sort();
}

int can(int qsz, int qarr[]) {
	std::sort(qarr,qarr+qsz);
	if (qsz > BLK_SIZE || x <= BLK_SIZE) {
		std::priority_queue<int, std::vector<int>, std::greater<int>> pq;

		int scanline = 0;
		for (int i = 0; i < qsz; i++) {
			while (scanline < segments.size() && segments[scanline].first <= qarr[i]) {
				pq.emplace(segments[scanline].second);
				++scanline;
			}

			while (!pq.empty()&&pq.top()<qarr[i]) {
				pq.pop();
			}

			int count = 0;
			while (!pq.empty()&&count<qarr[i]) {
				++count;
				pq.pop();
			}

			if (count != qarr[i]) {
				return 0;
			}
		}

		return 1;
	}
	else {
		std::map<int,int> freq;
		std::vector<int> distinct;
		for (int i = 0; i < qsz; i++) {
			++freq[qarr[i]];
			if (i+1<qsz&&qarr[i]==qarr[i+1]) {
				continue;
			}
			distinct.emplace_back(qarr[i]);
		}

		std::vector<std::pair<int,int>> updates;

		int ret = 1;
		for (int i = 0; i < distinct.size(); i++) {
			int target = 1LL * freq[distinct[i]] * distinct[i];
			for (int j = i; j < distinct.size() && target > 0; j++) {
				int ri = ((j+1<distinct.size()) ? distinct[j+1]-1 : x);

				int add = std::min(target, tree_query(distinct[i],distinct[i],ri) - fnwk_query(ri) + fnwk_query(distinct[i]-1));
				target -= add;

				updates.emplace_back(ri,add);
				fnwk_add(ri,add);
			}

			if (target != 0) {
				//std::cout << i << "\n";
				ret = 0;
				break;
			}
		}

		for (const auto& [a, b] : updates) {
			fnwk_add(a,-b);
		}

		return ret;
	}
}

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