oj.uz

Submission #908516

# Submission time Handle Problem Language Result Execution time Memory
908516 2024-01-16T13:20:12 Z daoquanglinh2007 Segments (IZhO18_segments) C++17
59 / 100
 2531 ms 34884 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define isz(a) (int)(a).size()
 
const int NM = 1e5, BL = 10000, 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 4 ms 12632 KB Output is correct
2 Correct 4 ms 12632 KB Output is correct
3 Correct 34 ms 12636 KB Output is correct
4 Correct 28 ms 12636 KB Output is correct
5 Correct 21 ms 12776 KB Output is correct
6 Correct 24 ms 12636 KB Output is correct
7 Correct 27 ms 12632 KB Output is correct
8 Correct 22 ms 12888 KB Output is correct
9 Correct 20 ms 12636 KB Output is correct
10 Correct 11 ms 12636 KB Output is correct
11 Correct 32 ms 12788 KB Output is correct
12 Correct 32 ms 12636 KB Output is correct
13 Correct 8 ms 12636 KB Output is correct
14 Correct 25 ms 12756 KB Output is correct
15 Correct 26 ms 12760 KB Output is correct
16 Correct 28 ms 12632 KB Output is correct
17 Correct 24 ms 12780 KB Output is correct
18 Correct 15 ms 12784 KB Output is correct
19 Correct 24 ms 12632 KB Output is correct
20 Correct 24 ms 12632 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1351 ms 24860 KB Output is correct
2 Correct 1472 ms 24752 KB Output is correct
3 Correct 1276 ms 24720 KB Output is correct
4 Correct 1515 ms 25812 KB Output is correct
5 Correct 1827 ms 34356 KB Output is correct
6 Correct 1835 ms 34252 KB Output is correct
7 Correct 1503 ms 24908 KB Output is correct
8 Correct 1292 ms 24768 KB Output is correct
9 Correct 1278 ms 25120 KB Output is correct
10 Correct 732 ms 17564 KB Output is correct
11 Correct 920 ms 19540 KB Output is correct
12 Correct 1791 ms 30340 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 1270 ms 13220 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 1063 ms 13128 KB Output is correct
2 Correct 1050 ms 13164 KB Output is correct
3 Correct 1091 ms 13672 KB Output is correct
4 Correct 1066 ms 13320 KB Output is correct
5 Correct 2109 ms 31412 KB Output is correct
6 Correct 722 ms 16216 KB Output is correct
7 Correct 1674 ms 33040 KB Output is correct
8 Correct 793 ms 17948 KB Output is correct
9 Correct 1527 ms 21752 KB Output is correct
10 Correct 2204 ms 30248 KB Output is correct
11 Correct 1200 ms 15936 KB Output is correct
12 Correct 1612 ms 34284 KB Output is correct
13 Correct 2009 ms 25824 KB Output is correct
14 Correct 1567 ms 20016 KB Output is correct
15 Correct 2103 ms 33748 KB Output is correct
16 Correct 2037 ms 26924 KB Output is correct
17 Correct 1591 ms 24852 KB Output is correct
18 Correct 1390 ms 24852 KB Output is correct
19 Correct 1392 ms 24856 KB Output is correct
20 Correct 1500 ms 24956 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12632 KB Output is correct
2 Correct 4 ms 12632 KB Output is correct
3 Correct 34 ms 12636 KB Output is correct
4 Correct 28 ms 12636 KB Output is correct
5 Correct 21 ms 12776 KB Output is correct
6 Correct 24 ms 12636 KB Output is correct
7 Correct 27 ms 12632 KB Output is correct
8 Correct 22 ms 12888 KB Output is correct
9 Correct 20 ms 12636 KB Output is correct
10 Correct 11 ms 12636 KB Output is correct
11 Correct 32 ms 12788 KB Output is correct
12 Correct 32 ms 12636 KB Output is correct
13 Correct 8 ms 12636 KB Output is correct
14 Correct 25 ms 12756 KB Output is correct
15 Correct 26 ms 12760 KB Output is correct
16 Correct 28 ms 12632 KB Output is correct
17 Correct 24 ms 12780 KB Output is correct
18 Correct 15 ms 12784 KB Output is correct
19 Correct 24 ms 12632 KB Output is correct
20 Correct 24 ms 12632 KB Output is correct
21 Correct 1351 ms 24860 KB Output is correct
22 Correct 1472 ms 24752 KB Output is correct
23 Correct 1276 ms 24720 KB Output is correct
24 Correct 1515 ms 25812 KB Output is correct
25 Correct 1827 ms 34356 KB Output is correct
26 Correct 1835 ms 34252 KB Output is correct
27 Correct 1503 ms 24908 KB Output is correct
28 Correct 1292 ms 24768 KB Output is correct
29 Correct 1278 ms 25120 KB Output is correct
30 Correct 732 ms 17564 KB Output is correct
31 Correct 920 ms 19540 KB Output is correct
32 Correct 1791 ms 30340 KB Output is correct
33 Correct 1063 ms 13128 KB Output is correct
34 Correct 1050 ms 13164 KB Output is correct
35 Correct 1091 ms 13672 KB Output is correct
36 Correct 1066 ms 13320 KB Output is correct
37 Correct 2109 ms 31412 KB Output is correct
38 Correct 722 ms 16216 KB Output is correct
39 Correct 1674 ms 33040 KB Output is correct
40 Correct 793 ms 17948 KB Output is correct
41 Correct 1527 ms 21752 KB Output is correct
42 Correct 2204 ms 30248 KB Output is correct
43 Correct 1200 ms 15936 KB Output is correct
44 Correct 1612 ms 34284 KB Output is correct
45 Correct 2009 ms 25824 KB Output is correct
46 Correct 1567 ms 20016 KB Output is correct
47 Correct 2103 ms 33748 KB Output is correct
48 Correct 2037 ms 26924 KB Output is correct
49 Correct 1591 ms 24852 KB Output is correct
50 Correct 1390 ms 24852 KB Output is correct
51 Correct 1392 ms 24856 KB Output is correct
52 Correct 1500 ms 24956 KB Output is correct
53 Correct 1124 ms 13280 KB Output is correct
54 Correct 1080 ms 13260 KB Output is correct
55 Correct 1145 ms 13012 KB Output is correct
56 Correct 1102 ms 13120 KB Output is correct
57 Correct 1116 ms 20536 KB Output is correct
58 Correct 607 ms 15492 KB Output is correct
59 Correct 1964 ms 27236 KB Output is correct
60 Correct 590 ms 14984 KB Output is correct
61 Correct 2008 ms 26276 KB Output is correct
62 Correct 2300 ms 33796 KB Output is correct
63 Correct 1964 ms 34884 KB Output is correct
64 Correct 2531 ms 33744 KB Output is correct
65 Correct 1669 ms 17236 KB Output is correct
66 Correct 1436 ms 16436 KB Output is correct
67 Correct 1930 ms 27248 KB Output is correct
68 Correct 1900 ms 24108 KB Output is correct
69 Correct 1522 ms 24780 KB Output is correct
70 Correct 1446 ms 24900 KB Output is correct
71 Correct 1410 ms 25164 KB Output is correct
72 Correct 1220 ms 24836 KB Output is correct
73 Correct 1310 ms 18320 KB Output is correct
74 Correct 1462 ms 23844 KB Output is correct
75 Correct 1802 ms 34844 KB Output is correct
76 Correct 1789 ms 34260 KB Output is correct
77 Correct 1226 ms 13000 KB Output is correct
78 Correct 1263 ms 13148 KB Output is correct
79 Correct 1098 ms 13088 KB Output is correct
80 Correct 1067 ms 13176 KB Output is correct
81 Correct 1741 ms 23548 KB Output is correct
82 Correct 1361 ms 18240 KB Output is correct
83 Correct 1210 ms 15808 KB Output is correct
84 Correct 1657 ms 23812 KB Output is correct
85 Correct 1862 ms 27772 KB Output is correct
86 Correct 1858 ms 28752 KB Output is correct
87 Correct 1449 ms 21072 KB Output is correct
88 Correct 1203 ms 15864 KB Output is correct

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12632 KB Output is correct
2 Correct 4 ms 12632 KB Output is correct
3 Correct 34 ms 12636 KB Output is correct
4 Correct 28 ms 12636 KB Output is correct
5 Correct 21 ms 12776 KB Output is correct
6 Correct 24 ms 12636 KB Output is correct
7 Correct 27 ms 12632 KB Output is correct
8 Correct 22 ms 12888 KB Output is correct
9 Correct 20 ms 12636 KB Output is correct
10 Correct 11 ms 12636 KB Output is correct
11 Correct 32 ms 12788 KB Output is correct
12 Correct 32 ms 12636 KB Output is correct
13 Correct 8 ms 12636 KB Output is correct
14 Correct 25 ms 12756 KB Output is correct
15 Correct 26 ms 12760 KB Output is correct
16 Correct 28 ms 12632 KB Output is correct
17 Correct 24 ms 12780 KB Output is correct
18 Correct 15 ms 12784 KB Output is correct
19 Correct 24 ms 12632 KB Output is correct
20 Correct 24 ms 12632 KB Output is correct
21 Correct 1351 ms 24860 KB Output is correct
22 Correct 1472 ms 24752 KB Output is correct
23 Correct 1276 ms 24720 KB Output is correct
24 Correct 1515 ms 25812 KB Output is correct
25 Correct 1827 ms 34356 KB Output is correct
26 Correct 1835 ms 34252 KB Output is correct
27 Correct 1503 ms 24908 KB Output is correct
28 Correct 1292 ms 24768 KB Output is correct
29 Correct 1278 ms 25120 KB Output is correct
30 Correct 732 ms 17564 KB Output is correct
31 Correct 920 ms 19540 KB Output is correct
32 Correct 1791 ms 30340 KB Output is correct
33 Incorrect 1270 ms 13220 KB Output isn't correct
34 Halted 0 ms 0 KB -