Submission #1133531

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133531		Muhammet	Segments (IZhO18_segments)	C++17	0 / 100	2598 ms	59088 KiB

segments

#include "bits/stdc++.h"

using namespace std;

#define SZ(s) (int)s.size()
#define ff first
#define ss second

vector <int> st, stm;

vector <vector <int>> vc[2][2];

vector <pair<int,int>> v[2];

vector <pair<int,pair<int,int>>> s[2];

int bld(int nd, int l, int r, int t){
	if(l == r){
		st[nd] = s[t][l].ff;
		stm[nd] = s[t][l].ff;
		vc[t][0][nd].push_back(s[t][l].ss.ff);
		vc[t][1][nd].push_back(s[t][l].ss.ss);
		return st[nd];
	}
	int md = (l + r) / 2;
	st[nd] = min(bld(nd*2,l,md,t), bld(nd*2+1,md+1,r,t));
	stm[nd] = max(stm[nd*2], stm[nd*2+1]);
	vector <int> v1 = vc[t][0][nd*2], v2 = vc[t][0][nd*2+1];
	reverse(v1.begin(), v1.end()), reverse(v2.begin(), v2.end());
	while(SZ(v1) or SZ(v2)){
		if(!SZ(v2)){
			vc[t][0][nd].push_back(v1.back());
			v1.pop_back();
		}
		else if(!SZ(v1)){
			vc[t][0][nd].push_back(v2.back());
			v2.pop_back();
		}
		else if(v1.back() <= v2.back()){
			vc[t][0][nd].push_back(v1.back());
			v1.pop_back();
		}
		else {
			vc[t][0][nd].push_back(v2.back());
			v2.pop_back();
		}
	}
	v1 = vc[t][1][nd*2], v2 = vc[t][1][nd*2+1];
	reverse(v1.begin(), v1.end()), reverse(v2.begin(), v2.end());
	while(SZ(v1) or SZ(v2)){
		if(!SZ(v2)){
			vc[t][1][nd].push_back(v1.back());
			v1.pop_back();
		}
		else if(!SZ(v1)){
			vc[t][1][nd].push_back(v2.back());
			v2.pop_back();
		}
		else if(v1.back() <= v2.back()){
			vc[t][1][nd].push_back(v1.back());
			v1.pop_back();
		}
		else {
			vc[t][1][nd].push_back(v2.back());
			v2.pop_back();
		}
	}
	return st[nd];
}

int fnd(int nd, int l, int r, int t, int k, int x, int y){
	if(stm[nd] < k) return 0;
	if(st[nd] >= k){
		int x1 = (r-l+1);
		x1 -= (upper_bound(vc[t][1][nd].begin(), vc[t][1][nd].end(), x+k-2) - vc[t][1][nd].begin());
		x1 -= (SZ(vc[t][0][nd]) - (lower_bound(vc[t][0][nd].begin(), vc[t][0][nd].end(), y-k+2) - vc[t][0][nd].begin()));
		return x1;
	}
	int md = (l + r) / 2;
	return (fnd(nd*2,l,md,t,k,x,y) + fnd(nd*2+1,md+1,r,t,k,x,y));
}

int f(int l, int r, int t, int k){
	int ans = 0;
	for(auto [l1,r1] : v[t]){
		if((min(r1,r) - max(l1,l)) + 1 >= k) ans++;
	}
	if(SZ(s[t])) ans += fnd(1,0,SZ(s[t])-1,t,k,l,r);
	return ans;
}

int main(){
	ios::sync_with_stdio(false); cin.tie(nullptr);

	int n, t, ans = 0, ind = 0;
	cin >> n >> t;
	st.assign(n*4,0), stm.assign(n*4,0);
	pair<int,int> mp[n+1];
	int k1 = sqrt(n*log2(n));
	for(int i = 1; i <= n; i++){
		int t1;
		cin >> t1;
		if(t1 == 1){
			int a, b;
			cin >> a >> b;
			a = (a ^ (t * ans));
			b = (b ^ (t * ans));
			if(a > b) swap(a,b);
			mp[i] = {a,b};
			v[0].push_back({a,b});
		}
		if(t1 == 2){
			int id;
			cin >> id;
			v[1].push_back(mp[id]);
		}
		if(t1 == 3){
			int a, b, k;
			cin >> a >> b >> k;
			a = (a ^ (t * ans));
			b = (b ^ (t * ans));
			if(a > b) swap(a,b);
			ans = (f(a, b, 0, k)-f(a, b, 1, k));
			cout << ans << '\n';
		}
		if(i % k1 == 0){
			for(int i = 0; i < 2; i++){
				for(auto [l,r] : v[i]){
					s[i].push_back({r-l+1,{l,r}});
				}
				sort(s[i].begin(), s[i].end());
				vc[i][0].clear(), vc[i][1].clear();
				// cout << (SZ(s[i])+1)*8 << '\n';
				vc[i][0].resize((SZ(s[i])+1)*4), vc[i][1].resize((SZ(s[i])+1)*4);
				// cout << SZ(s[i]) << '\n';
				if(SZ(s[i])) bld(1,0,SZ(s[i])-1,i);
				v[i].clear();
			}
		}
	}
}

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