Submission #1143735

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143735		xnqs	Examination (JOI19_examination)	C++20	100 / 100	1377 ms	92284 KiB

examination

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

std::mt19937 rng(53);

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

	Node(int val = 0):
		size(1), val(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;

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

void UpdateNodeSize(Node* node) {
	if (!node) {
		return;
	}
	node->size = 1 + GetNodeSize(node->l) + GetNodeSize(node->r);
}

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;
		UpdateNodeSize(node);
	}
	else {
		SplitDriver(node->l, key);
		node->l = _aux_split_r;
		_aux_split_r = node;
		UpdateNodeSize(node);
	}
}

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

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;
		UpdateNodeSize(a);
	}
	else {
		MergeDriver(a,b->l);
		b->l = _aux_merge;
		_aux_merge = b;
		UpdateNodeSize(b);
	}
}

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 curr_pos = skipped + GetNodeSize(node->l);
	if (node->val >= val) {
		return std::min(curr_pos, LowerBound(node->l, val, skipped));
	}
	else {
		return LowerBound(node->r, val, curr_pos+1);
	}
}

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

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

int GetKth(Node* node, int k, int skipped = 0) {
	if (!node) {
		return -1;
	}

	int curr_pos = skipped + GetNodeSize(node->l);
	if (k==curr_pos) {
		return node->val;
	}
	else if (k<curr_pos) {
		return GetKth(node->l,k,skipped);
	}
	else {
		return GetKth(node->r,k,curr_pos+1);
	}
}

Node* InsertValue(Node*& node, int val) {
	if (!node) {
		return node = new Node(val);
	}

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

Node* RemoveValue(Node*& node, int val) {
	if (!node) {
		return node;
	}

	int pos = LowerBound(node, val);
	auto trees = Split(node, pos);
	auto trees_right = Split(trees.second, 1);
	if (!trees_right.first||trees_right.first->val!=val) {
		return node;
	}

	node = Merge(trees.first, trees_right.second);
	delete trees_right.first;

	return node;
}
}; // namespace Treap

class FenwickFuckery {
private:
	std::vector<Treap::Node*> bit;
public:
	FenwickFuckery(int n = 0) {
		bit.assign(n, nullptr);
	}

	void Insert(int x, int y) {
		while (x < bit.size()) {
			bit[x] = Treap::InsertValue(bit[x], y);
			x += x&-x;
		}
	}

	// <= x, >= y
	int Query(int x, int y) {
		int ret = 0;
		while (x > 0) {
			int tmp = std::min(Treap::GetNodeSize(bit[x]), Treap::LowerBound(bit[x], y));
			ret += Treap::GetNodeSize(bit[x]) - tmp;
			x ^= x&-x;
		}
		return ret;
	}
};

struct Point {
	int x, y, s;
	Point():
		x(0), y(0), s(0) {}
	Point(int x, int y):
		x(x), y(y), s(x+y) {}
};

struct Query {
	int tgt_x, tgt_y, pfx, idx, sgn;
	Query():
		tgt_x(0), tgt_y(0), pfx(0), idx(0), sgn(0) {}
	Query(int tgt_x, int tgt_y, int pfx, int idx, int sgn):
		tgt_x(tgt_x), tgt_y(tgt_y), pfx(pfx), idx(idx), sgn(sgn) {}
};

int n, q;
std::vector<Point> arr;
std::vector<Query> queries;

void read_points() {
	std::cin >> n >> q;
	arr.reserve(n);
	for (int i = 0, a, b; i < n; i++) {
		std::cin >> a >> b;
		arr.emplace_back(a,b);
	}
}

void sort_points() {
	std::sort(arr.begin(),arr.end(),[](const Point& a, const Point& b) {
		return a.s < b.s;
	});
}

void read_queries() {
	for (int i = 0, x, y, z; i < q; i++) {
		std::cin >> x >> y >> z;
		queries.emplace_back(x,y,2000000005,i,1);
		queries.emplace_back(x,y,z-1,i,-1);
	}
}

void sort_queries() {
	std::sort(queries.begin(),queries.end(),[](const Query& a, const Query& b) {
		return a.pfx < b.pfx;
	});
}

void normalize_points_and_queries() {
	std::map<int,int> map;
	for (auto& i : arr) {
		map[i.x] = 0;
	}
	for (auto& i : queries) {
		map[i.tgt_x] = 0;
	}

	int cnt = 0;
	for (auto& i : map) {
		i.second = ++cnt;
	}

	for (auto& i : arr) {
		i.x = map[i.x];
	}
	for (auto& i : queries) {
		i.tgt_x = map[i.tgt_x];
	}
}

void answer_queries() {
	std::vector<int> qans(q, 0);

	int scl = 0;
	FenwickFuckery fnwk(2*n+5);

	for (const auto& [tgt_x, tgt_y, pfx, idx, sgn] : queries) {
		//std::cout << tgt_x << " " << tgt_y << " " << pfx << " " << idx << " " << sgn << "\n";
		while (scl < arr.size() && arr[scl].s <= pfx) {
			//std::cout << arr[scl].x << " " << arr[scl].y << " " << arr[scl].s << "\n";
			fnwk.Insert(arr[scl].x, arr[scl].y);
			++scl;
		}
		//std::cout << "\n";

		qans[idx] += sgn * (fnwk.Query(2*n, tgt_y) - fnwk.Query(tgt_x-1, tgt_y));
	}

	for (const auto& i : qans) {
		std::cout << i << "\n";
	}
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	read_points();
	sort_points();
	read_queries();
	sort_queries();
	normalize_points_and_queries();
	answer_queries();
}

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57