oj.uz

Submission #908515

# Submission time Handle Problem Language Result Execution time Memory
908515 2024-01-16T13:19:45 Z daoquanglinh2007 Segments (IZhO18_segments) C++17
59 / 100
 4472 ms 36248 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define isz(a) (int)(a).size()
 
const int NM = 1e5, BL = 5000, inf = INT_MAX;
 
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];
vector <int> 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 find_pos_ll(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_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]), -b[i]+k[i]-2)
			          -get(node2, bit2, find_pos(arr, -k[i]), (a[i] < +inf-(k[i]-2) ? a[i]+k[i]-2 : +inf));
			          
			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 3 ms 12636 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 25 ms 12632 KB Output is correct
4 Correct 30 ms 12632 KB Output is correct
5 Correct 19 ms 12632 KB Output is correct
6 Correct 25 ms 12880 KB Output is correct
7 Correct 30 ms 12636 KB Output is correct
8 Correct 17 ms 12632 KB Output is correct
9 Correct 19 ms 12636 KB Output is correct
10 Correct 8 ms 12780 KB Output is correct
11 Correct 30 ms 12636 KB Output is correct
12 Correct 33 ms 12780 KB Output is correct
13 Correct 8 ms 12632 KB Output is correct
14 Correct 18 ms 12776 KB Output is correct
15 Correct 29 ms 12884 KB Output is correct
16 Correct 25 ms 12632 KB Output is correct
17 Correct 22 ms 12636 KB Output is correct
18 Correct 11 ms 12636 KB Output is correct
19 Correct 24 ms 12888 KB Output is correct
20 Correct 22 ms 12636 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2118 ms 25296 KB Output is correct
2 Correct 2128 ms 24968 KB Output is correct
3 Correct 2105 ms 25008 KB Output is correct
4 Correct 2330 ms 25788 KB Output is correct
5 Correct 3302 ms 35608 KB Output is correct
6 Correct 3355 ms 35872 KB Output is correct
7 Correct 2286 ms 25124 KB Output is correct
8 Correct 2180 ms 24692 KB Output is correct
9 Correct 2275 ms 25256 KB Output is correct
10 Correct 1050 ms 17840 KB Output is correct
11 Correct 1373 ms 19316 KB Output is correct
12 Correct 3404 ms 30144 KB Output is correct

Subtask #3
0 / 16.0

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

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 492 ms 13212 KB Output is correct
2 Correct 468 ms 12984 KB Output is correct
3 Correct 484 ms 13140 KB Output is correct
4 Correct 467 ms 13136 KB Output is correct
5 Correct 3540 ms 31740 KB Output is correct
6 Correct 765 ms 16724 KB Output is correct
7 Correct 3570 ms 33236 KB Output is correct
8 Correct 1006 ms 18192 KB Output is correct
9 Correct 1893 ms 21388 KB Output is correct
10 Correct 3440 ms 30692 KB Output is correct
11 Correct 864 ms 15836 KB Output is correct
12 Correct 3530 ms 35836 KB Output is correct
13 Correct 2846 ms 25796 KB Output is correct
14 Correct 1402 ms 19656 KB Output is correct
15 Correct 3657 ms 33800 KB Output is correct
16 Correct 2742 ms 26948 KB Output is correct
17 Correct 2598 ms 24932 KB Output is correct
18 Correct 2517 ms 25136 KB Output is correct
19 Correct 2735 ms 24728 KB Output is correct
20 Correct 2799 ms 25236 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 25 ms 12632 KB Output is correct
4 Correct 30 ms 12632 KB Output is correct
5 Correct 19 ms 12632 KB Output is correct
6 Correct 25 ms 12880 KB Output is correct
7 Correct 30 ms 12636 KB Output is correct
8 Correct 17 ms 12632 KB Output is correct
9 Correct 19 ms 12636 KB Output is correct
10 Correct 8 ms 12780 KB Output is correct
11 Correct 30 ms 12636 KB Output is correct
12 Correct 33 ms 12780 KB Output is correct
13 Correct 8 ms 12632 KB Output is correct
14 Correct 18 ms 12776 KB Output is correct
15 Correct 29 ms 12884 KB Output is correct
16 Correct 25 ms 12632 KB Output is correct
17 Correct 22 ms 12636 KB Output is correct
18 Correct 11 ms 12636 KB Output is correct
19 Correct 24 ms 12888 KB Output is correct
20 Correct 22 ms 12636 KB Output is correct
21 Correct 2118 ms 25296 KB Output is correct
22 Correct 2128 ms 24968 KB Output is correct
23 Correct 2105 ms 25008 KB Output is correct
24 Correct 2330 ms 25788 KB Output is correct
25 Correct 3302 ms 35608 KB Output is correct
26 Correct 3355 ms 35872 KB Output is correct
27 Correct 2286 ms 25124 KB Output is correct
28 Correct 2180 ms 24692 KB Output is correct
29 Correct 2275 ms 25256 KB Output is correct
30 Correct 1050 ms 17840 KB Output is correct
31 Correct 1373 ms 19316 KB Output is correct
32 Correct 3404 ms 30144 KB Output is correct
33 Correct 492 ms 13212 KB Output is correct
34 Correct 468 ms 12984 KB Output is correct
35 Correct 484 ms 13140 KB Output is correct
36 Correct 467 ms 13136 KB Output is correct
37 Correct 3540 ms 31740 KB Output is correct
38 Correct 765 ms 16724 KB Output is correct
39 Correct 3570 ms 33236 KB Output is correct
40 Correct 1006 ms 18192 KB Output is correct
41 Correct 1893 ms 21388 KB Output is correct
42 Correct 3440 ms 30692 KB Output is correct
43 Correct 864 ms 15836 KB Output is correct
44 Correct 3530 ms 35836 KB Output is correct
45 Correct 2846 ms 25796 KB Output is correct
46 Correct 1402 ms 19656 KB Output is correct
47 Correct 3657 ms 33800 KB Output is correct
48 Correct 2742 ms 26948 KB Output is correct
49 Correct 2598 ms 24932 KB Output is correct
50 Correct 2517 ms 25136 KB Output is correct
51 Correct 2735 ms 24728 KB Output is correct
52 Correct 2799 ms 25236 KB Output is correct
53 Correct 490 ms 13136 KB Output is correct
54 Correct 481 ms 13216 KB Output is correct
55 Correct 527 ms 13140 KB Output is correct
56 Correct 476 ms 13128 KB Output is correct
57 Correct 1646 ms 20400 KB Output is correct
58 Correct 583 ms 15328 KB Output is correct
59 Correct 3014 ms 27512 KB Output is correct
60 Correct 496 ms 14892 KB Output is correct
61 Correct 3117 ms 26556 KB Output is correct
62 Correct 4352 ms 33924 KB Output is correct
63 Correct 3955 ms 35656 KB Output is correct
64 Correct 4472 ms 34092 KB Output is correct
65 Correct 1197 ms 17240 KB Output is correct
66 Correct 1056 ms 16308 KB Output is correct
67 Correct 3212 ms 27172 KB Output is correct
68 Correct 2573 ms 23760 KB Output is correct
69 Correct 2665 ms 24892 KB Output is correct
70 Correct 2216 ms 25100 KB Output is correct
71 Correct 2235 ms 24924 KB Output is correct
72 Correct 2305 ms 24856 KB Output is correct
73 Correct 1366 ms 18520 KB Output is correct
74 Correct 2343 ms 23852 KB Output is correct
75 Correct 3450 ms 36248 KB Output is correct
76 Correct 3375 ms 35556 KB Output is correct
77 Correct 474 ms 13148 KB Output is correct
78 Correct 504 ms 13088 KB Output is correct
79 Correct 472 ms 13588 KB Output is correct
80 Correct 459 ms 13104 KB Output is correct
81 Correct 2192 ms 23212 KB Output is correct
82 Correct 1240 ms 18052 KB Output is correct
83 Correct 839 ms 15528 KB Output is correct
84 Correct 2275 ms 23428 KB Output is correct
85 Correct 2549 ms 27328 KB Output is correct
86 Correct 2882 ms 29172 KB Output is correct
87 Correct 1746 ms 21360 KB Output is correct
88 Correct 861 ms 15696 KB Output is correct

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 25 ms 12632 KB Output is correct
4 Correct 30 ms 12632 KB Output is correct
5 Correct 19 ms 12632 KB Output is correct
6 Correct 25 ms 12880 KB Output is correct
7 Correct 30 ms 12636 KB Output is correct
8 Correct 17 ms 12632 KB Output is correct
9 Correct 19 ms 12636 KB Output is correct
10 Correct 8 ms 12780 KB Output is correct
11 Correct 30 ms 12636 KB Output is correct
12 Correct 33 ms 12780 KB Output is correct
13 Correct 8 ms 12632 KB Output is correct
14 Correct 18 ms 12776 KB Output is correct
15 Correct 29 ms 12884 KB Output is correct
16 Correct 25 ms 12632 KB Output is correct
17 Correct 22 ms 12636 KB Output is correct
18 Correct 11 ms 12636 KB Output is correct
19 Correct 24 ms 12888 KB Output is correct
20 Correct 22 ms 12636 KB Output is correct
21 Correct 2118 ms 25296 KB Output is correct
22 Correct 2128 ms 24968 KB Output is correct
23 Correct 2105 ms 25008 KB Output is correct
24 Correct 2330 ms 25788 KB Output is correct
25 Correct 3302 ms 35608 KB Output is correct
26 Correct 3355 ms 35872 KB Output is correct
27 Correct 2286 ms 25124 KB Output is correct
28 Correct 2180 ms 24692 KB Output is correct
29 Correct 2275 ms 25256 KB Output is correct
30 Correct 1050 ms 17840 KB Output is correct
31 Correct 1373 ms 19316 KB Output is correct
32 Correct 3404 ms 30144 KB Output is correct
33 Incorrect 547 ms 13168 KB Output isn't correct
34 Halted 0 ms 0 KB -