oj.uz

Submission #908507

# Submission time Handle Problem Language Result Execution time Memory
908507 2024-01-16T13:11:31 Z daoquanglinh2007 Segments (IZhO18_segments) C++17
7 / 100
 4440 ms 47076 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define isz(a) (int)(a).size()

const int NM = 2e5, BL = 4000;

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;
vector <int> arr;
vector <ll> node1[NM+5], node2[NM+5];
vector <int> bit1[NM+5], bit2[NM+5];
int cnt[NM+5];

void fake_update(vector <ll> node[NM+5], int x, ll y){
	while (x <= sz){
		node[x].push_back(y);
		x += x & (-x);
	}
}

void update(vector <ll> node[NM+5], vector <int> bit[NM+5], int x, ll yy){
	while (x <= sz){
		int y = lower_bound(node[x].begin(), node[x].end(), yy)-node[x].begin()+1;
		while (y <= isz(node[x])){
			bit[x][y]++;
			y += y & (-y);
		}
		x += x & (-x);
	}
}

void update_cnt(int x){
	while (x <= sz){
		cnt[x]++;
		x += x & (-x);
	}
}

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 find_pos_ll(vector <ll> &v, ll 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 get(vector <ll> node[NM+5], vector <int> bit[NM+5], int x, ll yy){
	int res = 0;
	while (x > 0){
		int y = find_pos_ll(node[x], yy);
		while (y > 0){
			res += bit[x][y];
			y -= y & (-y);
		}
		x -= x & (-x);
	}
	return res;
}

int get_cnt(int x){
	int res = 0;
	while (x > 0){
		res += cnt[x];
		x -= x & (-x);
	}
	return res;
}

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]);
			lastans = get_cnt(find_pos(arr, -k[i]))-get(node1, bit1, find_pos(arr, -k[i]), (ll)-b[i]+k[i]-2)-get(node2, bit2, find_pos(arr, -k[i]), (ll)a[i]+k[i]-2);
			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){
			arr.clear();
			for (int j = 1; j <= num; j++)
				if (!del[j]){
					arr.push_back(-(r[j]-l[j]+1));
				}
			sort(arr.begin(), arr.end());
			arr.erase(unique(arr.begin(), arr.end()), arr.end());
			sz = isz(arr);
			for (int j = 1; j <= sz; j++){
				node1[j].clear();
				node2[j].clear();
			}
			for (int j = 1; j <= num; j++){
				if (del[j]) continue;
				int x = lower_bound(arr.begin(), arr.end(), -(r[j]-l[j]+1))-arr.begin()+1;
				fake_update(node1, x, -l[j]);
				fake_update(node2, x, r[j]);
			}
			for (int j = 1; j <= sz; j++){
				sort(node1[j].begin(), node1[j].end());
				sort(node2[j].begin(), node2[j].end());
				bit1[j].assign(isz(node1[j])+1, 0);
				bit2[j].assign(isz(node2[j])+1, 0);
			}
			memset(cnt, 0, sizeof(cnt));
			for (int j = 1; j <= num; j++){
				if (del[j]) continue;
				int x = lower_bound(arr.begin(), arr.end(), -(r[j]-l[j]+1))-arr.begin()+1;
				update(node1, bit1, x, -l[j]);
				update(node2, bit2, x, r[j]);
				update_cnt(x);
			}
		}
	}
	return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 22872 KB Output is correct
2 Correct 6 ms 23232 KB Output is correct
3 Correct 21 ms 23064 KB Output is correct
4 Correct 22 ms 23132 KB Output is correct
5 Correct 16 ms 24148 KB Output is correct
6 Correct 20 ms 23900 KB Output is correct
7 Correct 24 ms 23388 KB Output is correct
8 Correct 19 ms 23900 KB Output is correct
9 Correct 20 ms 23640 KB Output is correct
10 Correct 15 ms 24156 KB Output is correct
11 Correct 29 ms 23804 KB Output is correct
12 Correct 29 ms 23636 KB Output is correct
13 Correct 16 ms 24156 KB Output is correct
14 Correct 20 ms 23644 KB Output is correct
15 Correct 22 ms 23132 KB Output is correct
16 Correct 21 ms 23132 KB Output is correct
17 Correct 21 ms 23316 KB Output is correct
18 Correct 16 ms 23900 KB Output is correct
19 Correct 24 ms 23388 KB Output is correct
20 Correct 25 ms 23372 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2941 ms 38792 KB Output is correct
2 Correct 2876 ms 40944 KB Output is correct
3 Runtime error 2982 ms 41092 KB Memory limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 412 ms 24104 KB Output is correct
2 Correct 416 ms 24176 KB Output is correct
3 Correct 433 ms 24152 KB Output is correct
4 Correct 408 ms 24144 KB Output is correct
5 Runtime error 4316 ms 45548 KB Memory limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 359 ms 24092 KB Output is correct
2 Correct 368 ms 24144 KB Output is correct
3 Correct 360 ms 23892 KB Output is correct
4 Correct 373 ms 23928 KB Output is correct
5 Runtime error 4440 ms 47076 KB Memory limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 22872 KB Output is correct
2 Correct 6 ms 23232 KB Output is correct
3 Correct 21 ms 23064 KB Output is correct
4 Correct 22 ms 23132 KB Output is correct
5 Correct 16 ms 24148 KB Output is correct
6 Correct 20 ms 23900 KB Output is correct
7 Correct 24 ms 23388 KB Output is correct
8 Correct 19 ms 23900 KB Output is correct
9 Correct 20 ms 23640 KB Output is correct
10 Correct 15 ms 24156 KB Output is correct
11 Correct 29 ms 23804 KB Output is correct
12 Correct 29 ms 23636 KB Output is correct
13 Correct 16 ms 24156 KB Output is correct
14 Correct 20 ms 23644 KB Output is correct
15 Correct 22 ms 23132 KB Output is correct
16 Correct 21 ms 23132 KB Output is correct
17 Correct 21 ms 23316 KB Output is correct
18 Correct 16 ms 23900 KB Output is correct
19 Correct 24 ms 23388 KB Output is correct
20 Correct 25 ms 23372 KB Output is correct
21 Correct 2941 ms 38792 KB Output is correct
22 Correct 2876 ms 40944 KB Output is correct
23 Runtime error 2982 ms 41092 KB Memory limit exceeded
24 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 22872 KB Output is correct
2 Correct 6 ms 23232 KB Output is correct
3 Correct 21 ms 23064 KB Output is correct
4 Correct 22 ms 23132 KB Output is correct
5 Correct 16 ms 24148 KB Output is correct
6 Correct 20 ms 23900 KB Output is correct
7 Correct 24 ms 23388 KB Output is correct
8 Correct 19 ms 23900 KB Output is correct
9 Correct 20 ms 23640 KB Output is correct
10 Correct 15 ms 24156 KB Output is correct
11 Correct 29 ms 23804 KB Output is correct
12 Correct 29 ms 23636 KB Output is correct
13 Correct 16 ms 24156 KB Output is correct
14 Correct 20 ms 23644 KB Output is correct
15 Correct 22 ms 23132 KB Output is correct
16 Correct 21 ms 23132 KB Output is correct
17 Correct 21 ms 23316 KB Output is correct
18 Correct 16 ms 23900 KB Output is correct
19 Correct 24 ms 23388 KB Output is correct
20 Correct 25 ms 23372 KB Output is correct
21 Correct 2941 ms 38792 KB Output is correct
22 Correct 2876 ms 40944 KB Output is correct
23 Runtime error 2982 ms 41092 KB Memory limit exceeded
24 Halted 0 ms 0 KB -