Submission #379670

#	Time	Username	Problem	Language	Result	Execution time	Memory
379670		cheissmart	Segments (IZhO18_segments)	C++14	100 / 100	2395 ms	10780 KiB

segments

#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "Line(" << __LINE__ << ") -> " << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 2e5 + 7, K = 2000;

pi seg[N];
V<array<int, 3>> buf;
int alive[N], new_id = 1;
int tot = 0;
vi r_bucket[N / K + 1], l_bucket[N / K + 1];
V<array<int, 3>> all;

void rebuild() {
	if(tot) for(int i = 0; i <= (tot - 1) / K; i++)
		l_bucket[i].clear(), r_bucket[i].clear();
	tot = 0;
	all.clear();
	for(int i = 1; i < new_id; i++) if(alive[i]) {
		tot++;
		int l = seg[i].F, r = seg[i].S;
		all.PB({r - l, l, r});
	}
	sort(ALL(all));
	for(int i = 0; i < tot; i++) {
		l_bucket[i / K].PB(all[i][1]);
		r_bucket[i / K].PB(all[i][2]);
	}
	if(tot) for(int i = 0; i <= (tot - 1) / K; i++) {
		sort(ALL(l_bucket[i]));
		sort(ALL(r_bucket[i]));
	}
	buf.clear();
}

void add(int l, int r) {
	alive[new_id] = 1;
	seg[new_id] = {l, r};
	buf.PB({seg[new_id].F, seg[new_id].S, 1});
	new_id++;
	if(buf.size() > K) rebuild();
}

void del(int id) {
	alive[id] = 0;
	buf.PB({seg[id].F, seg[id].S, -1});
	if(buf.size() > K) rebuild();
}

int qry(int l, int r, int k) { // k is length
	if(r - l < k) return 0;
	int ans = tot;
	if(tot) for(int i = 0; i <= (tot - 1) / K; i++) {
		int lb = i * K, rb = min((i + 1) * K, tot);
		if(all[rb - 1][0] < k) {
			ans -= int(l_bucket[i].size());
			continue;
		}
		if(all[lb][0] >= k) {
			ans -= lower_bound(ALL(r_bucket[i]), l + k) - r_bucket[i].begin();
			ans -= int(l_bucket[i].size()) - (upper_bound(ALL(l_bucket[i]), r - k) - l_bucket[i].begin());
		} else {
			for(int j = lb; j < rb; j++) if(all[j][0] >= k) {
				if(all[j][2] < l + k) ans--;
				if(all[j][1] > r - k) ans--;
			} else {
				ans--;
			}
		}
	}
	for(auto p:buf) {
		int L = max(l, p[0]), R = min(r, p[1]);
		if(R - L >= k)
			ans += p[2];
	}
	return ans;
}

signed main()
{
	IO_OP;

	int n, t;
	cin >> n >> t;
	int ans = 0;
	for(int i = 0; i < n; i++) {
		int op;
		cin >> op;
		auto decode = [&] (int& a, int& b) {
			a ^= t * ans, b ^= t * ans;
			if(a > b) swap(a, b);
		};
		if(op == 1) {
			int a, b;
			cin >> a >> b;
			decode(a, b);
			add(a, b);
		} else if(op == 2) {
			int id;	
			cin >> id;
			del(id);
		} else {
			int a, b, k;
			cin >> a >> b >> k;
			decode(a, b);
			ans = qry(a, b, k - 1);
			cout << ans << '\n';
		}
	}
	
}

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