Submission #960927

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
960927	2024-04-11T08:54:56 Z	pragmatist	Segments (IZhO18_segments)	C++17	16 / 100	1711 ms	8740 KB

segments

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5+7;
const int K = 500;

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][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
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	600 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Incorrect	2 ms	604 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	758 ms	6300 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	48 ms	2088 KB	Output is correct
2	Correct	41 ms	1932 KB	Output is correct
3	Correct	47 ms	2192 KB	Output is correct
4	Correct	40 ms	2132 KB	Output is correct
5	Correct	1203 ms	8004 KB	Output is correct
6	Correct	978 ms	6688 KB	Output is correct
7	Correct	1080 ms	6860 KB	Output is correct
8	Correct	1625 ms	8740 KB	Output is correct
9	Correct	1701 ms	8716 KB	Output is correct
10	Correct	1348 ms	6860 KB	Output is correct
11	Correct	125 ms	2372 KB	Output is correct
12	Correct	1387 ms	7440 KB	Output is correct
13	Correct	1208 ms	6168 KB	Output is correct
14	Correct	675 ms	4324 KB	Output is correct
15	Correct	573 ms	3724 KB	Output is correct
16	Correct	399 ms	3272 KB	Output is correct
17	Correct	802 ms	5948 KB	Output is correct
18	Correct	803 ms	5896 KB	Output is correct
19	Correct	821 ms	6004 KB	Output is correct
20	Correct	809 ms	5852 KB	Output is correct
21	Correct	178 ms	2432 KB	Output is correct
22	Correct	848 ms	4812 KB	Output is correct
23	Correct	1087 ms	5608 KB	Output is correct
24	Correct	927 ms	4952 KB	Output is correct
25	Correct	44 ms	2152 KB	Output is correct
26	Correct	38 ms	2052 KB	Output is correct
27	Correct	42 ms	2068 KB	Output is correct
28	Correct	41 ms	2036 KB	Output is correct
29	Correct	1218 ms	5900 KB	Output is correct
30	Correct	1230 ms	6108 KB	Output is correct
31	Correct	1711 ms	8600 KB	Output is correct
32	Correct	1387 ms	6768 KB	Output is correct
33	Correct	1243 ms	6404 KB	Output is correct
34	Correct	602 ms	3772 KB	Output is correct
35	Correct	1059 ms	5524 KB	Output is correct
36	Correct	1292 ms	6896 KB	Output is correct