Submission #342174

#	Time	Username	Problem	Language	Result	Execution time	Memory
342174		_ani	Segments (IZhO18_segments)	C++17	100 / 100	3093 ms	21708 KiB

segments

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
using ll = long long;
const int len = 1469;
int d;
struct el {
	int l, r, id;
}segs[2 * 100002];
bool operator<(const el& a, const el& b) {
	return a.r - a.l < b.r - b.l;
}
vector<el> seg, add, dl;
int del[2 * 100002];
vector<int> bl[2 * 100002], br[2 * 100002];
void Decomp()
{
	for (int i = 0; i < seg.size(); i += len)
	{
		bl[i / len].clear();
		br[i / len].clear();
	}
	seg.clear();
	for (int i = 0; i < d; i++)
		if (del[i] == 0)
			seg.push_back(segs[i]);
	sort(seg.begin(), seg.end());
	add.clear();
	dl.clear();
	for (int i = 0; i < seg.size(); i++)
	{
		bl[i / len].push_back(seg[i].l);
		br[i / len].push_back(seg[i].r);
	}
	for (int i = 0; i < seg.size(); i += len)
	{
		sort(bl[i / len].begin(), bl[i / len].end());
		sort(br[i / len].begin(), br[i / len].end());
	}
}
int Cnt(int a, int b, int k)
{
	if (a > b - k + 1)
		return 0;
	int ind = lower_bound(seg.begin(), seg.end(), el{ 0, k - 1, 0 }) - seg.begin();
	int res = 0;
	for (auto ban : add)
			if (min(ban.r, b) - max(ban.l, a) + 1 >= k)
				res++;
	for (auto ban : dl)
			if (min(ban.r, b) - max(ban.l, a) + 1 >= k)
				res--;
	int ans = (int)seg.size() - ind;
	int l = ind / len;

	for (int i = ind, end = (l + 1) * len - 1; i <= min(end, (int)seg.size() - 1); i++)
		if (seg[i].r - seg[i].l + 1 >= k)
		{
			if (seg[i].r - k < a - 1)
				ans--;
			if (seg[i].l > b - k + 1)
				ans--;
		}
	for (int i = l + 1; i <= ((int)seg.size() - 1) / len; ++i)
	{
		auto x = upper_bound(bl[i].begin(), bl[i].end(), b - k + 1);
		ans -= (bl[i].end() - x);
		x = lower_bound(br[i].begin(), br[i].end(), a + k - 1);
		//if (x != br[i].end())
		ans -= (x - br[i].begin());
	}
	return ans + res;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int lastans = 0;
	int n, t;
	cin >> n >> t;
	for (int i = 0; i < n; i++)
	{
		if (i % len == 0)
			Decomp();
		int type;
		cin >> type;
		if (type == 1)
		{
			int a, b;
			cin >> a >> b;
			a = a ^ (t * lastans);
			b = b ^ (t * lastans);
			if (a > b)
				swap(a, b);
			del[d] = 0;
			add.push_back({ a,b,d });
			segs[d] = { a,b,d };
			d++;
		}
		else if (type == 2)
		{
			int id;
			cin >> id;
			id--;
			del[id] = 1;
			dl.push_back(segs[id]);
		}
		else
		{
			int a, b, k;
			cin >> a >> b >> k;
			a = a ^ (t * lastans);
			b = b ^ (t * lastans);
			if (a > b)
				swap(a, b);
			lastans = Cnt(a, b, k);
			cout << lastans << '\n';
		}
	}
	return 0;
}

Compilation message (stderr)

segments.cpp: In function 'void Decomp()':
segments.cpp:20:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<el>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for (int i = 0; i < seg.size(); i += len)
      |                  ~~^~~~~~~~~~~~
segments.cpp:32:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<el>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |  for (int i = 0; i < seg.size(); i++)
      |                  ~~^~~~~~~~~~~~
segments.cpp:37:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<el>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  for (int i = 0; i < seg.size(); i += len)
      |                  ~~^~~~~~~~~~~~

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