Submission #528741

#	Time	Username	Problem	Language	Result	Execution time	Memory
528741		vuhoanggiap	Segments (IZhO18_segments)	C++17	75 / 100	5023 ms	8104 KiB

segments

#include <bits/stdc++.h>
#define ii pair<int, int> 
#define fi first
#define se second 
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
using namespace std;

const int maxN = 2e5 + 5, blockSz = 500, maxCnt = (maxN + blockSz - 1) / blockSz; 
int q, t, idSeg;  
int l[maxN], r[maxN]; 
bool rem[maxN];  

vector<ii> R; 
int n, blockCnt; 
int mnR[maxCnt], mxR[maxCnt]; 
vector<ii> Block[maxCnt]; // change sz
vector<ii> BlockL[maxCnt]; 
vector<ii> cur;  

void reset() {
	for (auto T : cur)
		if (T.se)
			rem[T.fi] = true; 
	R.clear(), cur.clear(); 
	for (int i = 1; i <= idSeg; i++)
		if (!rem[i])
			R.pb({r[i], i}); 
	sort(all(R)); 
	n = R.size(); 
	blockCnt = (n + blockSz - 1) / blockSz; 
	for (int b = 0; b <= blockCnt; b++) {
		Block[b].clear(); 
		BlockL[b].clear(); 
	}
	for (int b = 0; b < blockCnt; b++) {
		for (int i = b * blockSz; i < min(n, (b + 1) * blockSz); i++) {
			int id = R[i].se; 
			Block[b].pb({r[id] - l[id] + 1, r[id]}); 
			BlockL[b].pb({l[id], r[id]}); 
			mxR[b] = r[id]; 
			if (i == b * blockSz)
				mnR[b] = r[id];  
 		}	
 		sort(all(Block[b])); 
 		sort(all(BlockL[b])); 
	}
}

int R_lessthan(int val) {
	return lower_bound(all(R), mp(val, -1)) - R.begin(); 
}

int length_lessthan(int rr, int k) {
	int id = 0, ans = 0; 
	while (id < blockCnt && mxR[id] <= rr) {
		ans += lower_bound(all(Block[id]), mp(k, -1)) - Block[id].begin(); 
		id++; 
	}
	for (auto T : Block[id])
		if (T.se <= rr && T.fi < k)
			ans++; 
	return ans; 
}

int bruh(int ll, int rr) {
	int id = blockCnt - 1; 
	int ans = 0; 
	while (id > 0 && mnR[id] > rr) {
		ans += (int)BlockL[id].size() - (upper_bound(all(BlockL[id]), mp(ll, INT_MAX)) - BlockL[id].begin());
		id--; 
	}
	for (auto T : BlockL[id])
		if (T.fi > ll && T.se > rr) 
			ans++; 
	return ans; 
}

int length_lessthan(int ll, int rr, int k) {
	return length_lessthan(rr, k) - length_lessthan(ll - 1, k); 
}

bool bad(int l1, int r1, int l2, int r2) { return r1 < l2 || r2 < l1; }

int query(int ll, int rr, int k) {
		// cout << "query: " << ll << ' ' << rr << ' ' << k << '\n'; 
	if (rr - ll + 1 < k)
		return 0; 
	int ans = n; 
	ans -= (R_lessthan(ll + k - 1) + length_lessthan(ll + k - 1, rr, k) + bruh(rr - k + 1, rr)); 
	if (ans < 0) {
		assert(false);  
	}
	// cout << n << ' ' << R_lessthan(ll + k - 1) << ' ' << length_lessthan(ll + k - 1, rr, k) << ' ' << bruh(rr - k + 1, rr) << '\n'; 
	// cout << "before cur: " << ans << '\n';
	for (auto T : cur)
		if (!k || (!bad(l[T.fi], r[T.fi], ll, rr) && min(r[T.fi], rr) - max(l[T.fi], ll) + 1 >= k))
			ans += (T.se ? -1 : 1); 
	return ans; 
}

signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0); 
	cin >> q >> t; 
	for (int i = 1, lastAns = 0; i <= q; i++) {
		if (!(i % blockSz))
			reset(); 
		int type; cin >> type; 
		if (type == 1) {
			idSeg++; cin >> l[idSeg] >> r[idSeg]; 
			l[idSeg] ^= t * lastAns; 
			r[idSeg] ^= t * lastAns; 
			if (l[idSeg] > r[idSeg])
				swap(l[idSeg], r[idSeg]);
			cur.pb({idSeg, 0}); 
		}
		else if (type == 2) {
			int remId; cin >> remId; 
			cur.pb({remId, 1}); 
		}
		else {
			int ll, rr, k; cin >> ll >> rr >> k;  
			ll ^= t * lastAns; 
			rr ^= t * lastAns; 
			if (ll > rr)
				swap(ll, rr);
			cout << (lastAns = query(ll, rr, k)) << '\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