Submission #1088486

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088486		xnqs	Segments (IZhO18_segments)	C++17	7 / 100	3312 ms	65536 KiB

segments

// first time implementing batching btw
// because nsqrtlog is apparently better nlog^2
// because it uses less memory, gg nice logic
// WTF?? BRUTE FORCE GETS 75 BUT NLOG^2 WITH 
// MERGE SORT TREAP GETS 7 BECAUSE MEMORY LOL
// oh ffs here we go again using a merge sort fking tree
// instead of sqrt decomp even though its the same overall complexity

#ifndef LOCAL
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#endif

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <map>
#include <random>
 
const int BLK_SIZE = 450;
int q, t;
std::pair<int,int> seg[200005];
std::vector<int> arr_l;
std::vector<int> arr_r;
std::vector<int> arr_len;
std::vector<int> mst_r[800005];
std::vector<int> mst_len[800005];
bool in_ds[200005];
bool active[200005];
bool to_remove[200005];
std::vector<int> brute1;
std::vector<int> brute2;
 
int intersection_size(int l1, int r1, int l2, int r2) {
	return std::min(r1,r2) - std::max(l1,l2) + 1;
}

void build_tree(std::vector<int>* mst, const std::vector<int>& arr, int node, int l, int r) {
	if (l==r) {
		mst[node].emplace_back(arr[l]);
		return;
	}

	int m = (l+r)>>1;
	build_tree(mst,arr,node<<1,l,m);
	build_tree(mst,arr,node<<1|1,m+1,r);
	std::merge(mst[node<<1].begin(),mst[node<<1].end(),
	           mst[node<<1|1].begin(),mst[node<<1|1].end(),
	           std::back_inserter(mst[node]));
}

int query_gteq(std::vector<int>* mst, int node, int l, int r, int st, int fi, int val) {
	if (l>fi||r<st) {
		return 0;
	}
	if (st<=l&&r<=fi) {
		return mst[node].size() - (std::lower_bound(mst[node].begin(),mst[node].end(),val)-mst[node].begin());
	}

	int m = (l+r)>>1;
	return query_gteq(mst,node<<1,l,m,st,fi,val) + query_gteq(mst,node<<1|1,m+1,r,st,fi,val);
}
 
void recalculate() {
	std::vector<int> tmp;
	for (int i = 1; i <= q; i++) {
		if (active[i]&&!to_remove[i]) {
			tmp.emplace_back(i);
			//arr_l.emplace_back(seg[i].l);
			//arr_r.emplace_back(seg[i].r);
		}
	}
 
	std::sort(tmp.begin(),tmp.end(),[&](int a, int b) {
		if (seg[a].first!=seg[b].first) return seg[a].first < seg[b].first;
		return seg[a].second < seg[b].second;
	});
	
	// cleanup
	brute1.clear();
	brute2.clear();
	arr_l.clear();
	arr_r.clear();
	arr_len.clear();
	for (int i = 1; i <= q; i++) {
		in_ds[i] = 0;
		to_remove[i] = 0;
	}
	for (int i = 0; i < 800005; i++) {
		mst_r[i].clear();
		mst_len[i].clear();
	}
 
	for (const auto& i : tmp) {
		in_ds[i] = 1;
		arr_l.emplace_back(seg[i].first);
		arr_r.emplace_back(seg[i].second);
		arr_len.emplace_back(seg[i].second-seg[i].first+1);
	}
	build_tree(mst_r,arr_r,1,0,arr_l.size()-1);
	build_tree(mst_len,arr_len,1,0,arr_l.size()-1);
}
 
int brute_answer(int l, int r, int k) {
	int ret = 0;
	for (const auto& i : brute1) {
		ret += (intersection_size(l,r,seg[i].first,seg[i].second)>=k);
	}
	return ret;
}
 
int brute_answer2(int l, int r, int k) {
	int ret = 0;
	for (const auto& i : brute2) {
		ret += (intersection_size(l,r,seg[i].first,seg[i].second)>=k);
	}
	return ret;
}
 
int ds_answer(int l, int r, int k) {
	if (!arr_l.size()) {
		return 0;
	}

	const auto bs1 = [&]() {
		int ret = arr_r.size();
		int ll = 0, rr = arr_r.size()-1;
		while (ll<=rr) {
			int m = (ll+rr)>>1;
			if (arr_l[m]>=l) {
				ret = m;
				rr = m-1;
			}
			else {
				ll = m+1;
			}
		}
		return ret;
	};
	const auto bs2 = [&]() {
		int ret = -1;
		int ll = 0, rr = arr_r.size()-1;
		while (ll<=rr) {
			int m = (ll+rr)>>1;
			if (arr_l[m]<=r-k+1) {
				ret = m;
				ll = m+1;
			}
			else {
				rr = m-1;
			}
		}
		return ret;
	};
	const auto bs3 = [&]() {
		int ret = -1;
		int ll = 0, rr = arr_r.size()-1;
		while (ll<=rr) {
			int m = (ll+rr)>>1;
			if (arr_l[m]<l) {
				ret = m;
				ll = m+1;
			}
			else {
				rr = m-1;
			}
		}
		return ret;
	};
 
	// left segment inside [l, r]
	int ret = 0;
	int le = bs1();
	int ri = bs2();
	if (le<=ri) {
		ret += query_gteq(mst_len,1,0,arr_l.size()-1,le,ri,k);
	}
 
	// left segment outside [l, r]
	le = 0;
	ri = bs3();
	if (le<=ri) {
		ret += query_gteq(mst_r,1,0,arr_l.size()-1,le,ri,l+k-1);
	}
 
	return ret;
}
 
void print(const std::vector<int>& arr, const char* const msg) {
	std::cout << msg << ": ";
	for (const auto& i : arr) {
		std::cout << i << " ";
	}
	std::cout << "\n";
}
 
int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);
 
	std::cin >> q >> t;
	int last_ans = 0;
	int cnt = 0;
	for (int i = 0; i < q; i++) {
		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);
 
			++cnt;
			seg[cnt] = std::pair<int,int>(l,r);
			brute1.emplace_back(cnt);
			active[cnt] = 1;
		}
		else if (op==2) {
			int idx;
			std::cin >> idx;
 
			auto [l, r] = seg[idx];
 
			if (in_ds[idx]) {
				to_remove[idx] = 1;
				brute2.emplace_back(idx);
			}
			else {
				auto it = std::find(brute1.begin(),brute1.end(),idx);
				if (it!=brute1.end()) {
					brute1.erase(it);
				}
			}
			active[idx] = 0;
		}
		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 = ds_answer(l,r,k) + brute_answer(l,r,k) - brute_answer2(l,r,k);
			std::cout << (last_ans = ret) << "\n";
		}
	
#ifdef DBG
		print(arr_l,"arr_l");
		print(arr_r,"arr_r");
		print(arr_len,"arr_len");
		print(brute1,"brute1");
		print(brute2,"brute2");
		std::cout << "\n";
#endif
 
		if ((i+1)%BLK_SIZE==0) {
			recalculate();
		}
	}
 
#ifdef DBG
	print(arr_l,"arr_l");
	print(arr_r,"arr_r");
	print(arr_len,"arr_len");
	print(brute1,"brute1");
	print(brute2,"brute2");
	std::cout << "\n";
#endif
}

Compilation message (stderr)

segments.cpp: In function 'int main()':
segments.cpp:228:9: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
  228 |    auto [l, r] = seg[idx];
      |         ^~~~~~

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