Submission #1088497

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088497		xnqs	Segments (IZhO18_segments)	C++17	75 / 100	5067 ms	8796 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

#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> dcmp_r[455];
std::vector<int> dcmp_len[455];
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 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 < 455; i++) {
		dcmp_r[i].clear();
		dcmp_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);
		dcmp_r[(arr_l.size()-1)/BLK_SIZE].emplace_back(seg[i].second);
		dcmp_len[(arr_l.size()-1)/BLK_SIZE].emplace_back(seg[i].second-seg[i].first+1);
	}
 
	for (int i = 0; i < 455; i++) {
		std::sort(dcmp_r[i].begin(),dcmp_r[i].end());
		std::sort(dcmp_len[i].begin(),dcmp_len[i].end());
	}
}
 
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) {
	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) {
		int i = le;
		int iter = ((i%BLK_SIZE) ? BLK_SIZE - i%BLK_SIZE : 0);
		int blk = i/BLK_SIZE;
		while (i<=ri&&iter--) {
			ret += (arr_len[i]>=k);
			++i;
		}
		blk = i/BLK_SIZE;
		while (i+BLK_SIZE-1<=ri) {
			ret += static_cast<int>(dcmp_len[blk].size()) - (std::lower_bound(dcmp_len[blk].begin(),dcmp_len[blk].end(),k)-dcmp_len[blk].begin());
			i += BLK_SIZE;
			++blk;
		}
		while (i<=ri) {
			ret += (arr_len[i]>=k);
			++i;
		}
	}
 
	// left segment outside [l, r]
	le = 0;
	ri = bs3();
	if (le<=ri) {
		int i = le;
		int iter = ((i%BLK_SIZE) ? BLK_SIZE - i%BLK_SIZE : 0);
		int blk = i/BLK_SIZE;
		while (i<=ri&&iter--) {
			ret += (arr_r[i]>=l+k-1);
			++i;
		}
		blk = i/BLK_SIZE;
		while (i+BLK_SIZE-1<=ri) {
			ret += static_cast<int>(dcmp_r[blk].size()) - (std::lower_bound(dcmp_r[blk].begin(),dcmp_r[blk].end(),l+k-1)-dcmp_r[blk].begin());
			i += BLK_SIZE;
			++blk;
		}
		while (i<=ri) {
			ret += (arr_r[i]>=l+k-1);
			++i;
		}
	}
 
	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:233:9: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
  233 |    auto [l, r] = seg[idx];
      |         ^~~~~~

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