제출 #1133581

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1133581		Muhammet	Segments (IZhO18_segments)	C++17	100 / 100	1668 ms	6968 KiB

segments

#include "bits/stdc++.h"

using namespace std;

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

const int N = 2e5 + 5;

int k1, stmx[N][2], stmn[N][2];

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

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

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

void bld(int t){
	int cnt = -1;
	vector <int> v1, v2;
	vc[t][0].clear(), vc[t][1].clear();
	for(int i = 0; i < SZ(s[t]); i += k1){
		cnt++;
		v1.clear(), v2.clear();
		for(int j = i; j < min(i+k1,SZ(s[t])); j++){
			v1.push_back(s[t][j].ss.ff);
			v2.push_back(s[t][j].ss.ss);
		}
		stmn[cnt][t] = s[t][i].ff;
		stmx[cnt][t] = s[t][min(i+k1,SZ(s[t]))-1].ff;
		sort(v1.begin(), v1.end());
		sort(v2.begin(), v2.end());
		vc[t][0].push_back(v1);
		vc[t][1].push_back(v2);
	}
}

int fnd(int t, int k, int x, int y){
	int cnt = -1, ans = 0;
	for(int i = 0; i < SZ(s[t]); i += k1){
		cnt++;
		if(stmx[cnt][t] < k) continue;
		if(stmn[cnt][t] >= k){
			ans += (SZ(vc[t][0][cnt]));
			ans -= (upper_bound(vc[t][1][cnt].begin(), vc[t][1][cnt].end(), x+k-2) - vc[t][1][cnt].begin());
			ans -= (SZ(vc[t][0][cnt]) - (lower_bound(vc[t][0][cnt].begin(), vc[t][0][cnt].end(), y-k+2) - vc[t][0][cnt].begin()));
			continue;
		}
		for(int j = i; j < min(i+k1,SZ(s[t])); j++){
			if((min(s[t][j].ss.ss,y) - max(s[t][j].ss.ff,x)) + 1 >= k) ans++;
		}
	}
	return ans;
}

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++;
	}
	ans += fnd(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;
	pair<int,int> mp[n+1];
	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);
			ind++;
			mp[ind] = {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());
				bld(i);
				v[i].clear();
			}
		}
	}
}

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