Submission #1087731

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087731		xnqs	Segments (IZhO18_segments)	C++17	0 / 100	400 ms	65536 KiB

segments

// not enough memory for this, but oh well idfc its probably the most efficient solution time-wise

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

std::mt19937 rng(53);

template<typename Type>
class FenwickTree {
private:
	std::vector<Type> bit;
public:
	FenwickTree(int size = 0, Type val = 0) {
		assign(size,val);
	}
	void assign(int size = 0, Type val = 0) {
		bit.assign(size,0);
		if (size&&val) {
			for (int i = 1; i < size; i++) {
				bit[i] += val;
				if (i+(i&-i)<bit.size()) {
					bit[i+(i&-i)] += bit[i];
				}
			}
		}
	}

	void add(int poz, Type val) {
		while (poz<bit.size()) {
			bit[poz] += val;
			poz += poz&-poz;
		}
	}

	Type query(int poz) {
		Type ret = 0;
		while (poz>0) {
			ret += bit[poz];
			poz ^= poz&-poz;
		}
		return ret;
	}

	Type query(int l, int r) {
		return query(r) - query(l-1);
	}

	int binary_lifting(Type val) {
		int ret = 0;
		for (int step = 1<<18; step; step >>= 1) {
			if (ret+step<bit.size()&&val-bit[ret+step]>0) {
				val -= bit[ret+step];
				ret += step;
			}
		}
		return ++ret;
	}
};

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

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

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

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

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

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

	if (key<=NodeGetSize(node->l)) {
		SplitDriver(node->l,key);
		node->l = _aux_split_r;
		_aux_split_r = node;
		NodeUpdateSize(node);
	}
	else {
		SplitDriver(node->r,key-NodeGetSize(node->l)-1);
		node->r = _aux_split_l;
		_aux_split_l = node;
		NodeUpdateSize(node);
	}
}

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

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

Node* Insert(Node*& root, int pos, int val) {
	auto trees = Split(root, pos);
	return root = Merge(Merge(trees.first, new Node(val)), trees.second);
}

Node* Remove(Node*& root, int pos) {
	auto trees = Split(root,pos);
	auto trees_right = Split(trees.second,1);
	delete trees_right.first;
	return root = Merge(trees.first,trees_right.second);
}

int GetVal(Node* root, int pos, int skipped = 0) {
	auto trees = Treap::Split(root,pos);
	auto trees_right = Treap::Split(trees.second,1);
	int ret = trees_right.first->val;
	trees.second = Treap::Merge(trees_right.first,trees_right.second);
	root = Treap::Merge(trees.first,trees.second);
	return ret;
}

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

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

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

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

void Inorder(Node* node, int depth = 0) {
	if (!node) {
		return;
	}

	Inorder(node->l,depth+1);
	std::cout << node->val << " ";
	Inorder(node->r,depth+1);
	
	if (!depth) {
		std::cout << "\n";
	}
}
}; // namespace Treap

class SetBootleg {
private:
	Treap::Node* root = nullptr;
	void Print(Treap::Node* node, int depth = 0) {
		if (!node) {
			return;
		}

		Print(node->l,depth+1);
		std::cout << node->val << " ";
		Print(node->r,depth+1);

		if (!depth) {
			std::cout << "\n";
		}
	}
public:
	void Insert(int val) {
		if (!root) {
			root = new Treap::Node(val);
			return;
		}

		int pos = Treap::LowerBound(root,val);
		Treap::Insert(root,pos,val);
	}

	void Remove(int val) {
		if (!root) {
			return;
		}

		int pos = Treap::LowerBound(root,val);
		if (Treap::GetVal(root,pos)!=val) {
			return;
		}

		Treap::Remove(root,pos);
	}

	int LowerBound(int val) {
		return Treap::LowerBound(root,val);
	}
	int UpperBound(int val) {
		return Treap::UpperBound(root,val);
	}

	int Size() {
		return Treap::NodeGetSize(root);
	}

	void Print() {
		Print(root);
	}
}; // class SetBootleg

struct SegTreeNode {
	SetBootleg set;
	SegTreeNode* l = nullptr;
	SegTreeNode* r = nullptr;
};

int q, t;
FenwickTree<int> fnwk(200005,1);
SegTreeNode* mst1 = new SegTreeNode; // keeps length of segment in l, so if arr[l] = val, the segment is [l, l+val-1]
SegTreeNode* mst2 = new SegTreeNode; // keeps right side of segment in l
std::pair<int,int> seg[200005];
std::map<std::pair<int,int>,int> map;

void insert(SegTreeNode* node, uint32_t l, uint32_t r, uint32_t pos, int val) {
	node->set.Insert(val);
	if (l==r) {
		return;
	}

	auto m = (l+r)/2;
	if (pos<=m) {
		if (!node->l) node->l = new SegTreeNode;
		insert(node->l,l,m,pos,val);
	}
	else {
		if (!node->r) node->r = new SegTreeNode;
		insert(node->r,m+1,r,pos,val);
	}
}

void remove(SegTreeNode* node, uint32_t l, uint32_t r, uint32_t pos, int val) {
	if (!node) {
		return;
	}

	node->set.Remove(val);
	if (l==r) {
		return;
	}

	auto m = (l+r)/2;
	if (pos<=m) {
		remove(node->l,l,m,pos,val);
	}
	else {
		remove(node->r,m+1,r,pos,val);
	}
}

int query_gteq(SegTreeNode* node, uint32_t l, uint32_t r, uint32_t st, uint32_t fi, int val) {
	if (!node) {
		return 0;
	}
	if (l>fi||r<st) {
		return 0;
	}
	if (st<=l&&r<=fi) {
		return node->set.Size() - node->set.LowerBound(val);
	}

	auto m = (l+r)/2;
	return query_gteq(node->l,l,m,st,fi,val) + query_gteq(node->r,m+1,r,st,fi,val);
}

int main() {
#ifdef DBG
	//Treap::Node* root = nullptr;
	SetBootleg pl;
	while (1) {
		/*int op;
		std::cin >> op;
		if (op==1) {
			int pos, val;
			std::cin >> pos >> val;
			root = Treap::Merge(root, new Treap::Node(val));
			//Treap::Insert(root,pos,val);
		}
		else {
			int pos;
			std::cin >> pos;
			Treap::Remove(root,pos);
		}

		Treap::Inorder(root);*/

		int op;
		std::cin >> op;
		if (op==1) {
			int val;
			std::cin >> val;
			pl.Insert(val);
		}
		else {
			int val;
			std::cin >> val;
			pl.Remove(val);
		}

		std::cout << pl.Size() << "\n";
		pl.Print();
	}
#endif

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

	std::cin >> q >> t;
	int last_ans = 0;
	while (q--) {
		int op;
		std::cin >> op;
		if (op==1) {
			int a, b;
			std::cin >> a >> b;

			int l = a^(t*last_ans);
			int r = b^(t*last_ans);
			if (l>r) std::swap(l,r);

			int idx = fnwk.binary_lifting(1);
			fnwk.add(idx,-1);
			seg[idx] = std::pair<int,int>(l,r);
			map[std::pair<int,int>(l,r)] = idx;

			insert(mst1,0,2000000000,l,r-l+1);
			insert(mst2,0,2000000000,l,r);
		}
		else if (op==2) {
			int idx;
			std::cin >> idx;

			fnwk.add(idx,1);
			auto [l, r] = seg[idx];
			remove(mst1,0,2000000000,l,r-l+1);
			remove(mst2,0,2000000000,l,r);
		}
		else {
			int a, b, k;
			std::cin >> a >> b >> k;

			int l = a^(t*last_ans);
			int r = b^(t*last_ans);
			if (l>r) std::swap(l,r);

			int ret = query_gteq(mst1,0,2000000000,l,r-k+1,k);
			if (l>0) {
				ret += query_gteq(mst2,0,2000000000,0,l-1,l+k-1);
			}

			last_ans = ret;
			std::cout << ret << "\n";
		}
	}
}

Compilation message (stderr)

segments.cpp: In instantiation of 'int FenwickTree<Type>::binary_lifting(Type) [with Type = int]':
segments.cpp:388:35:   required from here
segments.cpp:57:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int, std::allocator<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |    if (ret+step<bit.size()&&val-bit[ret+step]>0) {
      |        ~~~~~~~~^~~~~~~~~~~
segments.cpp: In instantiation of 'void FenwickTree<Type>::add(int, Type) [with Type = int]':
segments.cpp:389:19:   required from here
segments.cpp:35:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int, std::allocator<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   while (poz<bit.size()) {
      |          ~~~^~~~~~~~~~~
segments.cpp: In instantiation of 'void FenwickTree<Type>::assign(int, Type) [with Type = int]':
segments.cpp:20:3:   required from 'FenwickTree<Type>::FenwickTree(int, Type) [with Type = int]'
segments.cpp:275:31:   required from here
segments.cpp:27:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int, std::allocator<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     if (i+(i&-i)<bit.size()) {
      |         ~~~~~~~~^~~~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 15
• Subtask 3: 0 / 16
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20
• Subtask 6: 0 / 25