Submission #1088065

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088065		xnqs	Segments (IZhO18_segments)	C++17	0 / 100	414 ms	4960 KiB

segments

// first time implementing batching btw
// because nsqrtlog is apparently better nlog^2
// because it uses less memory, gg nice logic

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

const int BLK_SIZE = 455;
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::max(0, 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[i/BLK_SIZE].emplace_back(seg[i].second);
		dcmp_len[i/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;
		while (i<=ri&&i%BLK_SIZE) {
			ret += (arr_len[i]>=k);
			++i;
		}
		while (i+BLK_SIZE-1<=ri) {
			ret += static_cast<int>(dcmp_len[i/BLK_SIZE].size()) - (std::lower_bound(dcmp_len[i/BLK_SIZE].begin(),dcmp_len[i/BLK_SIZE].end(),k)-dcmp_len[i/BLK_SIZE].begin());
			i += BLK_SIZE;
		}
		while (i<=r) {
			ret += (arr_len[i]>=k);
			++i;
		}
	}

	// left segment outside [l, r]
	le = 0;
	ri = bs3();
	if (le<=ri) {
		int i = le;
		while (i<=ri&&i%BLK_SIZE) {
			ret += (arr_r[i]>=l+k-1);
			++i;
		}
		while (i+BLK_SIZE-1<=ri) {
			ret += static_cast<int>(dcmp_r[i/BLK_SIZE].size()) - (std::lower_bound(dcmp_r[i/BLK_SIZE].begin(),dcmp_r[i/BLK_SIZE].end(),l+k-1)-dcmp_r[i/BLK_SIZE].begin());
			i += BLK_SIZE;
		}
		while (i<=r) {
			ret += (arr_r[i]>=l+k-1);
			++i;
		}
	}

	return ret;
}

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);
				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";
		}

		if ((i+1)%BLK_SIZE==0) {
			recalculate();
		}
	}
}

Compilation message (stderr)

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

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