oj.uz

Submission #908531

# Submission time Handle Problem Language Result Execution time Memory
908531 2024-01-16T13:38:35 Z daoquanglinh2007 Segments (IZhO18_segments) C++17
59 / 100
 1859 ms 36308 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 3 ms 12636 KB Output is correct
3 Correct 25 ms 12888 KB Output is correct
4 Correct 28 ms 12632 KB Output is correct
5 Correct 19 ms 12888 KB Output is correct
6 Correct 24 ms 12888 KB Output is correct
7 Correct 30 ms 13132 KB Output is correct
8 Correct 17 ms 12892 KB Output is correct
9 Correct 19 ms 12892 KB Output is correct
10 Correct 9 ms 12896 KB Output is correct
11 Correct 33 ms 13168 KB Output is correct
12 Correct 31 ms 12892 KB Output is correct
13 Correct 10 ms 12788 KB Output is correct
14 Correct 19 ms 12632 KB Output is correct
15 Correct 31 ms 13140 KB Output is correct
16 Correct 26 ms 12636 KB Output is correct
17 Correct 23 ms 12892 KB Output is correct
18 Correct 11 ms 12892 KB Output is correct
19 Correct 24 ms 12888 KB Output is correct
20 Correct 23 ms 12888 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1256 ms 26824 KB Output is correct
2 Correct 1286 ms 26372 KB Output is correct
3 Correct 1226 ms 26184 KB Output is correct
4 Correct 1354 ms 27256 KB Output is correct
5 Correct 1760 ms 35676 KB Output is correct
6 Correct 1685 ms 35660 KB Output is correct
7 Correct 1197 ms 26416 KB Output is correct
8 Correct 1174 ms 26412 KB Output is correct
9 Correct 1466 ms 26416 KB Output is correct
10 Correct 777 ms 19500 KB Output is correct
11 Correct 1020 ms 21136 KB Output is correct
12 Correct 1859 ms 31688 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 1199 ms 14540 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 1055 ms 14560 KB Output is correct
2 Correct 1047 ms 14256 KB Output is correct
3 Correct 1079 ms 14672 KB Output is correct
4 Correct 1083 ms 14400 KB Output is correct
5 Correct 1788 ms 33096 KB Output is correct
6 Correct 673 ms 18096 KB Output is correct
7 Correct 1669 ms 34584 KB Output is correct
8 Correct 722 ms 19560 KB Output is correct
9 Correct 1467 ms 23060 KB Output is correct
10 Correct 1737 ms 31564 KB Output is correct
11 Correct 1225 ms 17348 KB Output is correct
12 Correct 1606 ms 35564 KB Output is correct
13 Correct 1629 ms 27380 KB Output is correct
14 Correct 1360 ms 20868 KB Output is correct
15 Correct 1691 ms 35048 KB Output is correct
16 Correct 1637 ms 28556 KB Output is correct
17 Correct 1208 ms 26296 KB Output is correct
18 Correct 1250 ms 26408 KB Output is correct
19 Correct 1200 ms 26472 KB Output is correct
20 Correct 1255 ms 26272 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 3 ms 12636 KB Output is correct
3 Correct 25 ms 12888 KB Output is correct
4 Correct 28 ms 12632 KB Output is correct
5 Correct 19 ms 12888 KB Output is correct
6 Correct 24 ms 12888 KB Output is correct
7 Correct 30 ms 13132 KB Output is correct
8 Correct 17 ms 12892 KB Output is correct
9 Correct 19 ms 12892 KB Output is correct
10 Correct 9 ms 12896 KB Output is correct
11 Correct 33 ms 13168 KB Output is correct
12 Correct 31 ms 12892 KB Output is correct
13 Correct 10 ms 12788 KB Output is correct
14 Correct 19 ms 12632 KB Output is correct
15 Correct 31 ms 13140 KB Output is correct
16 Correct 26 ms 12636 KB Output is correct
17 Correct 23 ms 12892 KB Output is correct
18 Correct 11 ms 12892 KB Output is correct
19 Correct 24 ms 12888 KB Output is correct
20 Correct 23 ms 12888 KB Output is correct
21 Correct 1256 ms 26824 KB Output is correct
22 Correct 1286 ms 26372 KB Output is correct
23 Correct 1226 ms 26184 KB Output is correct
24 Correct 1354 ms 27256 KB Output is correct
25 Correct 1760 ms 35676 KB Output is correct
26 Correct 1685 ms 35660 KB Output is correct
27 Correct 1197 ms 26416 KB Output is correct
28 Correct 1174 ms 26412 KB Output is correct
29 Correct 1466 ms 26416 KB Output is correct
30 Correct 777 ms 19500 KB Output is correct
31 Correct 1020 ms 21136 KB Output is correct
32 Correct 1859 ms 31688 KB Output is correct
33 Correct 1055 ms 14560 KB Output is correct
34 Correct 1047 ms 14256 KB Output is correct
35 Correct 1079 ms 14672 KB Output is correct
36 Correct 1083 ms 14400 KB Output is correct
37 Correct 1788 ms 33096 KB Output is correct
38 Correct 673 ms 18096 KB Output is correct
39 Correct 1669 ms 34584 KB Output is correct
40 Correct 722 ms 19560 KB Output is correct
41 Correct 1467 ms 23060 KB Output is correct
42 Correct 1737 ms 31564 KB Output is correct
43 Correct 1225 ms 17348 KB Output is correct
44 Correct 1606 ms 35564 KB Output is correct
45 Correct 1629 ms 27380 KB Output is correct
46 Correct 1360 ms 20868 KB Output is correct
47 Correct 1691 ms 35048 KB Output is correct
48 Correct 1637 ms 28556 KB Output is correct
49 Correct 1208 ms 26296 KB Output is correct
50 Correct 1250 ms 26408 KB Output is correct
51 Correct 1200 ms 26472 KB Output is correct
52 Correct 1255 ms 26272 KB Output is correct
53 Correct 1070 ms 14476 KB Output is correct
54 Correct 1073 ms 14544 KB Output is correct
55 Correct 1064 ms 14344 KB Output is correct
56 Correct 1059 ms 14532 KB Output is correct
57 Correct 932 ms 22192 KB Output is correct
58 Correct 572 ms 17488 KB Output is correct
59 Correct 1375 ms 28932 KB Output is correct
60 Correct 586 ms 16560 KB Output is correct
61 Correct 1632 ms 27856 KB Output is correct
62 Correct 1711 ms 35524 KB Output is correct
63 Correct 1691 ms 36308 KB Output is correct
64 Correct 1740 ms 35244 KB Output is correct
65 Correct 1309 ms 18776 KB Output is correct
66 Correct 1229 ms 17492 KB Output is correct
67 Correct 1652 ms 28356 KB Output is correct
68 Correct 1576 ms 25312 KB Output is correct
69 Correct 1247 ms 26308 KB Output is correct
70 Correct 1214 ms 26512 KB Output is correct
71 Correct 1212 ms 26436 KB Output is correct
72 Correct 1254 ms 26272 KB Output is correct
73 Correct 1284 ms 19728 KB Output is correct
74 Correct 1563 ms 25540 KB Output is correct
75 Correct 1561 ms 36028 KB Output is correct
76 Correct 1677 ms 35544 KB Output is correct
77 Correct 1065 ms 14480 KB Output is correct
78 Correct 1081 ms 14628 KB Output is correct
79 Correct 1072 ms 14700 KB Output is correct
80 Correct 1050 ms 14340 KB Output is correct
81 Correct 1582 ms 24472 KB Output is correct
82 Correct 1305 ms 19712 KB Output is correct
83 Correct 1199 ms 17180 KB Output is correct
84 Correct 1578 ms 25048 KB Output is correct
85 Correct 1649 ms 28656 KB Output is correct
86 Correct 1771 ms 30348 KB Output is correct
87 Correct 1487 ms 22516 KB Output is correct
88 Correct 1215 ms 17096 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 3 ms 12636 KB Output is correct
3 Correct 25 ms 12888 KB Output is correct
4 Correct 28 ms 12632 KB Output is correct
5 Correct 19 ms 12888 KB Output is correct
6 Correct 24 ms 12888 KB Output is correct
7 Correct 30 ms 13132 KB Output is correct
8 Correct 17 ms 12892 KB Output is correct
9 Correct 19 ms 12892 KB Output is correct
10 Correct 9 ms 12896 KB Output is correct
11 Correct 33 ms 13168 KB Output is correct
12 Correct 31 ms 12892 KB Output is correct
13 Correct 10 ms 12788 KB Output is correct
14 Correct 19 ms 12632 KB Output is correct
15 Correct 31 ms 13140 KB Output is correct
16 Correct 26 ms 12636 KB Output is correct
17 Correct 23 ms 12892 KB Output is correct
18 Correct 11 ms 12892 KB Output is correct
19 Correct 24 ms 12888 KB Output is correct
20 Correct 23 ms 12888 KB Output is correct
21 Correct 1256 ms 26824 KB Output is correct
22 Correct 1286 ms 26372 KB Output is correct
23 Correct 1226 ms 26184 KB Output is correct
24 Correct 1354 ms 27256 KB Output is correct
25 Correct 1760 ms 35676 KB Output is correct
26 Correct 1685 ms 35660 KB Output is correct
27 Correct 1197 ms 26416 KB Output is correct
28 Correct 1174 ms 26412 KB Output is correct
29 Correct 1466 ms 26416 KB Output is correct
30 Correct 777 ms 19500 KB Output is correct
31 Correct 1020 ms 21136 KB Output is correct
32 Correct 1859 ms 31688 KB Output is correct
33 Incorrect 1199 ms 14540 KB Output isn't correct
34 Halted 0 ms 0 KB -