Submission #41726

#	Time	Username	Problem	Language	Result	Execution time	Memory
41726		aome	Segments (IZhO18_segments)	C++14	75 / 100	5059 ms	40960 KiB

segments

#include <bits/stdc++.h>
using namespace std;

const int N = 200005;
const int B = 1250;

int n, t, sz, lastans;
int cnt;
int L[N], R[N];
bool del[N];
vector<int> buf_add;
vector<int> buf_del;
vector<int> block_l[500];
vector<int> block_r[500];
vector< pair<int, int> > go;

void prep() {
	go.clear();
	for (int i = 1; i <= sz; ++i) {
		if (!del[i]) go.push_back(make_pair(R[i] - L[i] + 1, i));
	}
	sort(go.begin(), go.end());
	buf_add.clear(), buf_del.clear();
	int m = go.size();
	for (int i = 0; i <= m / B; ++i) block_l[i].clear(), block_r[i].clear();
	for (int i = 0; i < m; ++i) block_l[i / B].push_back(L[go[i].second]);
	for (int i = 0; i < m; ++i) block_r[i / B].push_back(R[go[i].second]); 
	for (int i = 0; i <= m / B; ++i) {
		sort(block_l[i].begin(), block_l[i].end());
		sort(block_r[i].begin(), block_r[i].end());
	}
}

int calc(int id, int l, int r) {
	// count number of commont points betweeen L[id], R[id] and l, r
	if (L[id] > l) return max(0, min(r, R[id]) - L[id] + 1);
	return max(0, min(R[id], r) - l + 1);
}

int calL(int l, int r, int x) {
	// count number of segments from l -> r which has L > x
	int res = 0;
	int bl = l / B, br = r / B;
	if (bl == br) {
		for (int i = l; i <= r; ++i) res += L[go[i].second] > x;
		return res;
	}
	for (int i = bl + 1; i < br; ++i) {
		int tmp = lower_bound(block_l[i].begin(), block_l[i].end(), x + 1) - block_l[i].begin();
		res += B - tmp;
	}
	for (int i = l; i < (bl + 1) * B; ++i) res += L[go[i].second] > x;
	for (int i = br * B; i <= r; ++i) res += L[go[i].second] > x;
	return res;
}

int calR(int l, int r, int x) {
	// count number of segments from l -> r which has R < x
	int res = 0;
	int bl = l / B, br = r / B;
	if (bl == br) {
		for (int i = l; i <= r; ++i) res += R[go[i].second] < x;
		return res;
	}
	for (int i = bl + 1; i < br; ++i) {
		int tmp = lower_bound(block_r[i].begin(), block_r[i].end(), x) - block_r[i].begin();
		res += tmp;
	}
	for (int i = l; i < (bl + 1) * B; ++i) res += R[go[i].second] < x;
	for (int i = br * B; i <= r; ++i) res += R[go[i].second] < x;
	return res;
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> t;
	for (int i = 1; i <= n; ++i) {
		if (i % B == 0) prep();

		int type; cin >> type;

		if (type == 1) {
			int l, r; cin >> l >> r;
			l = l ^ (1LL * t * lastans);
			r = r ^ (1LL * t * lastans);
			if (l > r) swap(l, r);
			++sz, L[sz] = l, R[sz] = r, buf_add.push_back(sz), cnt++;
		}

		if (type == 2) {
			int x; cin >> x, buf_del.push_back(x), del[x] = 1, cnt--;
		}

		if (type == 3) {
			int l, r, k; 
			cin >> l >> r >> k;
			l = l ^ (1LL * t * lastans);
			r = r ^ (1LL * t * lastans);
			if (l > r) swap(l, r);

			if (r - l + 1 < k) {
				lastans = 0, cout << "0\n"; continue;
			} 

			int res = 0;	

			// cout << "#add\n";
			// for (auto j : buf_add) cout << j << ' '; cout << '\n';
			// cout << "#del\n";
			// for (auto j : buf_del) cout << j << ' '; cout << '\n';

			for (auto j : buf_add) res += calc(j, l, r) < k;
			for (auto j : buf_del) res -= calc(j, l, r) < k;
			int p = lower_bound(go.begin(), go.end(), make_pair(k, 0)) - go.begin();

			// cout << "#go\n";
			// for (auto i : go) cout << i.second << ' '; cout << '\n';
			// cout << "#p " << p << '\n';

			// number of segments r - l + 1 < k
			res += p;

			// query p -> go.size() - 1 (segments with size >= k)

			// count number of segments L > r - k + 1
			res += calL(p, go.size() - 1, r - k + 1);
			// count number of segments R < l + k - 1
			res += calR(p, go.size() - 1, l + k - 1);

			// cout << "#l-r " << l << ' ' << r << '\n';
			// cout << "# " << res << '\n';

			res = cnt - res, lastans = res;
			cout << res << '\n';
		}
	}
}

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