Submission #960974

#	Time	Username	Problem	Language	Result	Execution time	Memory
960974		pragmatist	Segments (IZhO18_segments)	C++17	100 / 100	4128 ms	18944 KiB

segments

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 2e5+7;
const int K = 1000;
 
int n, t;
pair<int, int> a[N];
multiset<pair<int, int> > active;
 
struct Data {
	int l, r, x;
};
vector<Data> add;
vector<array<int, 3>> cur;
vector<int> b1[1000], b2[1000];
	
void build() {
    cur.clear();
	for(auto [x, y] : active) {
		int len = y-x+1;
		cur.push_back({len, x, y});		
	}	
	sort(cur.begin(), cur.end());
	int m = (int)cur.size();
	for(int i = 0; i <= (m-1)/K; ++i) {
		b1[i].clear();
		b2[i].clear();
	}
	for(int i = 0; i < m; ++i) {
		b1[i/K].push_back(cur[i][1]);
		b2[i/K].push_back(cur[i][2]);				
	}
	for(int i = 0; i <= (m-1)/K; ++i) {
		sort(b1[i].rbegin(), b1[i].rend());
		sort(b2[i].begin(), b2[i].end());
	}
	add.clear();
}
 
int get(int l, int r, int k) {
	if(r-l+1<k) {
		return 0;
	}		
	int res = 0;
	int m = (int)cur.size();
	for(int i = 0, id = 0; i < m; i += K, ++id) {
		if(cur[i][0]<k) {
		    int j = min(m, i+K), old = i;
		    if(cur[j-1][0]<k) {
		    	continue;
		    }
		    while(i<j) {
		    	if(cur[i][0]>=k) {
		    		res++;
		    		if(cur[i][2]<l+k-1) {
		    			res--;
		    		}            
		    		if(cur[i][1]>r-k+1) {
		    			res--;
		    		}
		    	}
		    	i++;
		    }
			i = old;
			continue;
		} else {
			res += (int)(b1[id].size());
			assert((int)b1[id].size() == (int)b2[id].size());
			int tl = 0, tr = (int)b1[id].size()-1, x1 = 0, x2 = 0;
			while(tl<=tr) {
				int mid = (tl+tr)/2;
				if(b1[id][mid]>r-k+1) {
					x1 = mid+1;
					tl = mid+1;
				} else {
					tr = mid-1;
				}
			} 
			res -= x1;
			tl = 0, tr = (int)b2[id].size()-1;
			while(tl<=tr) {
				int mid = (tl+tr)/2;
				if(b2[id][mid]<l+k-1) {
					x2 = mid+1;
					tl = mid+1;
				} else {
					tr = mid-1;
				}
			}			
			res -= x2;
		}
	} 
	for(auto [c, d, x] : add) {
		int len = min(d, r)-max(l, c)+1;
		if(len >= k) {
			res += x;
		}
	}
	return res;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
	cin >> n >> t;
	int ans = 0, timer = 0;
	for(int i = 1; i <= n; ++i) {
		char tp;
		cin >> tp;
		if(tp == '1') {
			int l, r;
			cin >> l >> r;
			l = (l^(t*ans));
			r = (r^(t*ans));
			if(l>r) {
				swap(l, r);
			}
			a[++timer] = {l, r};
			add.push_back({l, r, 1});
			active.insert({l, r});		
		} else if(tp == '2') {
			int id;
			cin >> id;
			add.push_back({a[id].first, a[id].second, -1});
			auto it = active.find(a[id]);
			active.erase(it);
		} else {
			int l, r, k;
			cin >> l >> r >> k;
			l = (l^(t*ans));
			r = (r^(t*ans));
			if(l>r) {
				swap(l, r);
			}
			if(r-l+1<k) {
				cout << (ans=0) << "\n";
				continue;
			}
			cout << (ans = get(l, r, k)) << "\n";
		}
		if((int)add.size()>K) {
			build();
		}
	}
	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