oj.uz

Submission #908501

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

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

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

void update(vector <int> node[NM+5], vector <int> bit[NM+5], int x, int 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 get(vector <int> node[NM+5], vector <int> bit[NM+5], int x, int yy){
	int res = 0;
	while (x > 0){
		int y = find_pos(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;
}

signed 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]), -b[i]+k[i]-2)-get(node2, bit2, find_pos(arr, -k[i]), 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 8 ms 29016 KB Output is correct
2 Correct 8 ms 29020 KB Output is correct
3 Correct 24 ms 29216 KB Output is correct
4 Correct 24 ms 29212 KB Output is correct
5 Correct 17 ms 30300 KB Output is correct
6 Correct 20 ms 30300 KB Output is correct
7 Correct 24 ms 29524 KB Output is correct
8 Correct 20 ms 30044 KB Output is correct
9 Correct 22 ms 30040 KB Output is correct
10 Correct 16 ms 30300 KB Output is correct
11 Correct 31 ms 30032 KB Output is correct
12 Correct 32 ms 30044 KB Output is correct
13 Correct 16 ms 30300 KB Output is correct
14 Correct 21 ms 30040 KB Output is correct
15 Correct 24 ms 29276 KB Output is correct
16 Correct 24 ms 29396 KB Output is correct
17 Correct 23 ms 29720 KB Output is correct
18 Correct 17 ms 30296 KB Output is correct
19 Correct 23 ms 29532 KB Output is correct
20 Correct 24 ms 29788 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 3383 ms 48176 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 442 ms 30216 KB Output is correct
2 Correct 429 ms 30352 KB Output is correct
3 Correct 438 ms 30364 KB Output is correct
4 Correct 420 ms 30184 KB Output is correct
5 Runtime error 4538 ms 56944 KB Memory limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 378 ms 30236 KB Output is correct
2 Correct 383 ms 30120 KB Output is correct
3 Correct 376 ms 30032 KB Output is correct
4 Correct 392 ms 30032 KB Output is correct
5 Runtime error 4782 ms 58460 KB Memory limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 29016 KB Output is correct
2 Correct 8 ms 29020 KB Output is correct
3 Correct 24 ms 29216 KB Output is correct
4 Correct 24 ms 29212 KB Output is correct
5 Correct 17 ms 30300 KB Output is correct
6 Correct 20 ms 30300 KB Output is correct
7 Correct 24 ms 29524 KB Output is correct
8 Correct 20 ms 30044 KB Output is correct
9 Correct 22 ms 30040 KB Output is correct
10 Correct 16 ms 30300 KB Output is correct
11 Correct 31 ms 30032 KB Output is correct
12 Correct 32 ms 30044 KB Output is correct
13 Correct 16 ms 30300 KB Output is correct
14 Correct 21 ms 30040 KB Output is correct
15 Correct 24 ms 29276 KB Output is correct
16 Correct 24 ms 29396 KB Output is correct
17 Correct 23 ms 29720 KB Output is correct
18 Correct 17 ms 30296 KB Output is correct
19 Correct 23 ms 29532 KB Output is correct
20 Correct 24 ms 29788 KB Output is correct
21 Runtime error 3383 ms 48176 KB Memory limit exceeded
22 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 29016 KB Output is correct
2 Correct 8 ms 29020 KB Output is correct
3 Correct 24 ms 29216 KB Output is correct
4 Correct 24 ms 29212 KB Output is correct
5 Correct 17 ms 30300 KB Output is correct
6 Correct 20 ms 30300 KB Output is correct
7 Correct 24 ms 29524 KB Output is correct
8 Correct 20 ms 30044 KB Output is correct
9 Correct 22 ms 30040 KB Output is correct
10 Correct 16 ms 30300 KB Output is correct
11 Correct 31 ms 30032 KB Output is correct
12 Correct 32 ms 30044 KB Output is correct
13 Correct 16 ms 30300 KB Output is correct
14 Correct 21 ms 30040 KB Output is correct
15 Correct 24 ms 29276 KB Output is correct
16 Correct 24 ms 29396 KB Output is correct
17 Correct 23 ms 29720 KB Output is correct
18 Correct 17 ms 30296 KB Output is correct
19 Correct 23 ms 29532 KB Output is correct
20 Correct 24 ms 29788 KB Output is correct
21 Runtime error 3383 ms 48176 KB Memory limit exceeded
22 Halted 0 ms 0 KB -