Submission #1163926

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163926		xnqs	Teams (IOI15_teams)	C++20	21 / 100	4102 ms	343312 KiB

teams

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

#include "teams.h"

std::mt19937 rng(53);

namespace Treap {
struct Node {
	int key;
	int64_t val;
	int size;
	int64_t sum;
	int prio;
	Node* l;
	Node* r;

	Node(int key = 0, int64_t val = 0):
		key(key), val(val), size(1), sum(val), prio(rng()), l(nullptr), r(nullptr) {}
	~Node() {
		if (l) delete l;
		if (r) delete r;
	}
};

Node* _aux_split_l = nullptr;
Node* _aux_split_r = nullptr;
Node* _aux_merge = nullptr;

inline int GetNodeSize(Node* node) {
	if (!node) {
		return 0;
	}
	return node->size;
}

inline int64_t GetNodeSum(Node* node) {
	if (!node) {
		return 0;
	}
	return node->sum;
}

inline void UpdateNode(Node* node) {
	node->size = 1;
	node->sum = node->val;

	if (node->l) {
		node->size += node->l->size;
		node->sum += node->l->sum;
	}
	if (node->r) {
		node->size += node->r->size;
		node->sum += node->r->sum;
	}
}

void SplitDriver(Node* node, int key) {
	if (!node) {
		_aux_split_l = _aux_split_r = nullptr;
		return;
	}

	if (key-GetNodeSize(node->l)-1>=0) {
		SplitDriver(node->r,key-GetNodeSize(node->l)-1);
		node->r = _aux_split_l;
		_aux_split_l = node;
		UpdateNode(node);
	}
	else {
		SplitDriver(node->l,key);
		node->l = _aux_split_r;
		_aux_split_r = node;
		UpdateNode(node);
	}
}

void MergeDriver(Node* a, Node* b) {
	if (!a) {
		_aux_merge = b;
		return;
	}
	if (!b) {
		_aux_merge = a;
		return;
	}

	if (a->prio > b->prio) {
		MergeDriver(a->r,b);
		a->r = _aux_merge;
		_aux_merge = a;
		UpdateNode(a);
	}
	else {
		MergeDriver(a,b->l);
		b->l = _aux_merge;
		_aux_merge = b;
		UpdateNode(b);
	}
}

inline std::pair<Node*, Node*> Split(Node* node, int key) {
	SplitDriver(node, key);
	return {_aux_split_l, _aux_split_r};
}

inline Node* Merge(Node* a, Node* b) {
	MergeDriver(a, b);
	return _aux_merge;
}

int LowerBound(Node* node, int val, int skipped = 0) {
	if (!node) {
		return 0x3f3f3f3f;
	}

	int node_key = skipped + GetNodeSize(node->l);
	if (node->key >= val) {
		return std::min(node_key, LowerBound(node->l, val, skipped));
	}
	else {
		return LowerBound(node->r, val, node_key+1);
	}
}

int UpperBound(Node* node, int val, int skipped = 0) {
	if (!node) {
		return 0x3f3f3f3f;
	}

	int node_key = skipped + GetNodeSize(node->l);
	if (node->key > val) {
		return std::min(node_key, UpperBound(node->l, val, skipped));
	}
	else {
		return UpperBound(node->r, val, node_key+1);
	}
}

Node* Insert(Node*& node, int pos, int key, int64_t val) {
	if (!node) {
		return node = new Node(key, val);
	}

	auto trees = Split(node, pos);
	return Merge(Merge(trees.first, new Node(key, val)), trees.second); 
}

int64_t RangeSumQuery(Node*& node, int l, int r) {
	if (!node) {
		return 0;
	}
	if (l>r) {
		return 0;
	}

	auto trees = Split(node, l);
	auto trees_right = Split(trees.second, r-l+1);

	int64_t ret = Treap::GetNodeSum(trees_right.first);
	node = Merge(Merge(trees.first,trees_right.first),trees_right.second);
	return ret;
}
}; // namespace Treap

const int BLK_SIZE = 300;

int x;
Treap::Node* tree[2000005];
std::vector<std::pair<int,int>> segments;

void tree_insert(int node, int l, int r, int pos, int key, int64_t val) {
	int p = std::min(Treap::GetNodeSize(tree[node]), Treap::LowerBound(tree[node], key));
	tree[node] = Treap::Insert(tree[node], p, key, val);

	if (l==r) {
		return;
	}

	int m = (l+r)>>1;
	if (pos<=m) {
		tree_insert(node<<1,l,m,pos,key,val);
	}
	else {
		tree_insert(node<<1|1,m+1,r,pos,key,val);
	}
}

int64_t tree_query(int node, int l, int r, int st, int fi, int kl, int kr) {
	if (l>fi||r<st) {
		return 0;
	}
	if (st<=l&&r<=fi) {
		int le = std::min(Treap::GetNodeSize(tree[node]), Treap::LowerBound(tree[node], kl));
		int ri = std::min(Treap::GetNodeSize(tree[node]), Treap::UpperBound(tree[node], kr))-1;

		if (le == Treap::GetNodeSize(tree[node])) {
			return 0;
		}
		return Treap::RangeSumQuery(tree[node], le, ri);
	}

	int m = (l+r)>>1;
	return tree_query(node<<1,l,m,st,fi,kl,kr) + tree_query(node<<1|1,m+1,r,st,fi,kl,kr);
}

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

	for (int i = 0; i < x; i++) {
		tree_insert(1,1,x,A[i],B[i],1);
		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;
	});

	//std::cout << tree_query(1,1,x,1,2,2,4) << "\n";
	//std::cout << tree_query(1,1,x,1,x,1,x) << "\n";
}

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::tuple<int,int,int64_t>> updates;

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

				int64_t add = std::min(target, tree_query(1,1,x,1,qarr[i],qarr[i],ri));
				target -= add;

				updates.emplace_back(1,ri,-add);
				tree_insert(1,1,x,1,ri,-add);
			}

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

		for (const auto& [a, b, c] : updates) {
			tree_insert(1,1,x,a,b,-c);
		}

		return ret;
	}
}

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