Submission #908919

#	Time	Username	Problem	Language	Result	Execution time	Memory
908919		daoquanglinh2007	Segments (IZhO18_segments)	C++17	100 / 100	2826 ms	39112 KiB

segments

#include <bits/stdc++.h>
using namespace std;
 
#define pii pair <int, int>
#define fi first
#define se second
#define mp make_pair
#define isz(a) (int)(a).size()
 
const int NM = 2e5, BL = 1e4, S = 450, inf = 2e9+11;
 
int n, t, type[NM+5], a[NM+5], b[NM+5], id[NM+5], k[NM+5], lastans = 0;
int num = 0, l[NM+5], r[NM+5];
bool del[NM+5];
int sz, sz1, sz2;
vector <pii> v;
vector <int> arr, arr1, arr2;
vector <pii> f[NM+5], g[NM+5], sf[S+5], sg[S+5];
int cnt[NM+5];
 
void update(vector <pii> f[NM+5], vector <pii> sf[S+5], int x, int y){
	if (f[x].empty()) f[x].push_back(mp(y, 1));
	else if (f[x].back().fi < y) f[x].push_back(mp(y, f[x].back().se+1));
	else f[x].back().se++;
	
	int sx = x/S;
	if (sf[sx].empty()) sf[sx].push_back(mp(y, 1));
	else if (sf[sx].back().fi < y) sf[sx].push_back(mp(y, sf[sx].back().se+1));
	else sf[sx].back().se++;
}
 
int get(vector <pii> f[NM+5], vector <pii> sf[S+5], int x, int y){
	int res = 0, z;
	for (int i = 0; i < x/S; i++){
		if (sf[i].empty() || y < sf[i][0].fi);
		else if (y >= sf[i].back().fi) res += sf[i].back().se;
		else{
			z = upper_bound(sf[i].begin(), sf[i].end(), mp(y, +inf))-sf[i].begin();
			res += sf[i][z-1].se;
		}
	}
	for (int i = x/S*S; i <= x; i++){
		if (f[i].empty() || y < f[i][0].fi);
		else if (y >= f[i].back().fi) res += f[i].back().se;
		else{
			z = upper_bound(f[i].begin(), f[i].end(), mp(y, +inf))-f[i].begin();
			res += f[i][z-1].se;
		}
	}
	return res;
}
 
void process(){
	v.clear();
	arr.clear();
	arr1.clear();
	arr2.clear();
	for (int i = 1; i <= num; i++)
		if (!del[i]){
			v.push_back(mp(l[i], r[i]));
			arr.push_back(-(r[i]-l[i]+1));
			arr1.push_back(-l[i]);
			arr2.push_back(r[i]);
		}
	sort(v.begin(), v.end(), [&](pii a, pii b){
		return a.se-a.fi+1 > b.se-b.fi+1;
	});	
	sort(arr.begin(), arr.end()); arr.erase(unique(arr.begin(), arr.end()), arr.end());
	sort(arr1.begin(), arr1.end()); arr1.erase(unique(arr1.begin(), arr1.end()), arr1.end());
	sort(arr2.begin(), arr2.end()); arr2.erase(unique(arr2.begin(), arr2.end()), arr2.end());
	
	sz = isz(arr), sz1 = isz(arr1), sz2 = isz(arr2);
	
	assert(sz <= NM);
	assert(sz1 <= NM);
	assert(sz2 <= NM);
	
	for (int i = 1; i <= sz1; i++) f[i].clear();
	for (int i = 1; i <= sz2; i++) g[i].clear();
	
	for (int i = 0; i <= S; i++){
		sf[i].clear();
		sg[i].clear();
	}
	
	memset(cnt, 0, sizeof(cnt));
	int j = 0;
	for (pii P : v){
		update(f, sf, lower_bound(arr1.begin(), arr1.end(), -P.fi)-arr1.begin()+1, -(P.se-P.fi+1));
		update(g, sg, lower_bound(arr2.begin(), arr2.end(), P.se)-arr2.begin()+1, -(P.se-P.fi+1));
		while (arr[j] < -(P.se-P.fi+1)) j++;
		cnt[j+1]++;
	}
	
	for (int i = 1; i <= sz; i++) cnt[i] += cnt[i-1];
}
 
int find_pos(vector <int> &v, int x){
	if (v.empty()) return 0;
	if (x < v[0]) return 0;
	if (x >= v.back()) return isz(v);
	return upper_bound(v.begin(), v.end(), x)-v.begin();
}
 
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n >> t;
	for (int i = 0; i < n; i++){
		cin >> type[i];
		if (type[i] == 1){
			cin >> a[i] >> b[i];
			a[i] ^= (t*lastans), b[i] ^= (t*lastans);
			if (a[i] > b[i]) swap(a[i], b[i]);
			l[++num] = a[i], r[num] = b[i];
		}
		else if (type[i] == 2){
			cin >> id[i];
			del[id[i]] = 1;
		}
		else{
			cin >> a[i] >> b[i] >> k[i];
			a[i] ^= (t*lastans), b[i] ^= (t*lastans);
			if (a[i] > b[i]) swap(a[i], b[i]);
			if (b[i]-a[i]+1 < k[i]) lastans = 0;
			else{
				lastans = cnt[find_pos(arr, -k[i])]-get(f, sf, find_pos(arr1, -b[i]+k[i]-2), -k[i])
			          -get(g, sg, find_pos(arr2, a[i] < +inf-(k[i]-2) ? a[i]+k[i]-2 : +inf), -k[i]);
			          
				for (int j = i-i%BL; j < i; j++){
					if (type[j] == 1){
						int lo = max(a[j], a[i]), hi = min(b[j], b[i]);
						if (hi-lo+1 >= k[i]) lastans++;
					}
					else if (type[j] == 2){
						int lo = max(l[id[j]], a[i]), hi = min(r[id[j]], b[i]);
						if (hi-lo+1 >= k[i]) lastans--;
					}
				}
			}
			cout << lastans << '\n';
		}
		if (i%BL == BL-1 && i < n-1){
			process();
		}
	}
	return 0;
}

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