oj.uz

Submission #528744

# Submission time Handle Problem Language Result Execution time Memory
528744 2022-02-21T09:26:00 Z vuhoanggiap Segments (IZhO18_segments) C++17
100 / 100
 4645 ms 10904 KB 
#include <bits/stdc++.h>
#define ii pair<int, int> 
#define fi first
#define se second 
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
using namespace std;

const int maxN = 2e5 + 5, blockSz = 1000, maxCnt = (maxN + blockSz - 1) / blockSz; 
int q, t, idSeg;  
int l[maxN], r[maxN]; 
bool rem[maxN];  

vector<ii> R; 
int n, blockCnt; 
int mnR[maxCnt], mxR[maxCnt]; 
vector<ii> Block[maxCnt]; // change sz
vector<ii> BlockL[maxCnt]; 
vector<ii> cur;  

void reset() {
	for (auto T : cur)
		if (T.se)
			rem[T.fi] = true; 
	R.clear(), cur.clear(); 
	for (int i = 1; i <= idSeg; i++)
		if (!rem[i])
			R.pb({r[i], i}); 
	sort(all(R)); 
	n = R.size(); 
	blockCnt = (n + blockSz - 1) / blockSz; 
	for (int b = 0; b <= blockCnt; b++) {
		Block[b].clear(); 
		BlockL[b].clear(); 
	}
	for (int b = 0; b < blockCnt; b++) {
		for (int i = b * blockSz; i < min(n, (b + 1) * blockSz); i++) {
			int id = R[i].se; 
			Block[b].pb({r[id] - l[id] + 1, r[id]}); 
			BlockL[b].pb({l[id], r[id]}); 
			mxR[b] = r[id]; 
			if (i == b * blockSz)
				mnR[b] = r[id];  
 		}	
 		sort(all(Block[b])); 
 		sort(all(BlockL[b])); 
	}
}

int R_lessthan(int val) {
	return lower_bound(all(R), mp(val, -1)) - R.begin(); 
}

int length_lessthan(int rr, int k) {
	if (!blockCnt)
		return 0; 
	int id = 0, ans = 0; 
	while (id < blockCnt && mxR[id] <= rr) {
		ans += lower_bound(all(Block[id]), mp(k, -1)) - Block[id].begin(); 
		id++; 
	}
	for (auto T : Block[id])
		if (T.se <= rr && T.fi < k)
			ans++; 
	return ans; 
}

int bruh(int ll, int rr) {
	if (!blockCnt)
		return 0; 
	int id = blockCnt - 1; 
	int ans = 0; 
	while (id > 0 && mnR[id] > rr) {
		ans += (int)BlockL[id].size() - (upper_bound(all(BlockL[id]), mp(ll, INT_MAX)) - BlockL[id].begin());
		id--; 
	}
	for (auto T : BlockL[id])
		if (T.fi > ll && T.se > rr) 
			ans++; 
	return ans; 
}

int length_lessthan(int ll, int rr, int k) {
	return length_lessthan(rr, k) - length_lessthan(ll - 1, k); 
}

bool bad(int l1, int r1, int l2, int r2) { return r1 < l2 || r2 < l1; }

int query(int ll, int rr, int k) {
	if (rr - ll + 1 < k)
		return 0; 
	int ans = n; 
	ans -= (R_lessthan(ll + k - 1) + length_lessthan(ll + k - 1, rr, k) + bruh(rr - k + 1, rr)); 
	if (ans < 0) {
		assert(false);  
	}
	for (auto T : cur)
		if (!k || (!bad(l[T.fi], r[T.fi], ll, rr) && min(r[T.fi], rr) - max(l[T.fi], ll) + 1 >= k))
			ans += (T.se ? -1 : 1); 
	return ans; 
}

signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0); 
	cin >> q >> t; 
	for (int i = 1, lastAns = 0; i <= q; i++) {
		if (!(i % blockSz))
			reset(); 
		int type; cin >> type; 
		if (type == 1) {
			idSeg++; cin >> l[idSeg] >> r[idSeg]; 
			l[idSeg] ^= t * lastAns; 
			r[idSeg] ^= t * lastAns; 
			if (l[idSeg] > r[idSeg])
				swap(l[idSeg], r[idSeg]);
			cur.pb({idSeg, 0}); 
		}
		else if (type == 2) {
			int remId; cin >> remId; 
			cur.pb({remId, 1}); 
		}
		else {
			int ll, rr, k; cin >> ll >> rr >> k;  
			ll ^= t * lastAns; 
			rr ^= t * lastAns; 
			if (ll > rr)
				swap(ll, rr);
			cout << (lastAns = query(ll, rr, k)) << '\n'; 
		}
	}
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 5 ms 332 KB Output is correct
4 Correct 5 ms 332 KB Output is correct
5 Correct 7 ms 512 KB Output is correct
6 Correct 8 ms 508 KB Output is correct
7 Correct 8 ms 412 KB Output is correct
8 Correct 7 ms 480 KB Output is correct
9 Correct 7 ms 460 KB Output is correct
10 Correct 4 ms 460 KB Output is correct
11 Correct 11 ms 460 KB Output is correct
12 Correct 14 ms 476 KB Output is correct
13 Correct 5 ms 460 KB Output is correct
14 Correct 7 ms 460 KB Output is correct
15 Correct 7 ms 356 KB Output is correct
16 Correct 8 ms 368 KB Output is correct
17 Correct 12 ms 332 KB Output is correct
18 Correct 5 ms 460 KB Output is correct
19 Correct 7 ms 416 KB Output is correct
20 Correct 12 ms 440 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1041 ms 2320 KB Output is correct
2 Correct 1020 ms 2304 KB Output is correct
3 Correct 1008 ms 2344 KB Output is correct
4 Correct 1049 ms 2364 KB Output is correct
5 Correct 985 ms 3392 KB Output is correct
6 Correct 966 ms 3572 KB Output is correct
7 Correct 1026 ms 2436 KB Output is correct
8 Correct 1016 ms 2228 KB Output is correct
9 Correct 1018 ms 2488 KB Output is correct
10 Correct 651 ms 1364 KB Output is correct
11 Correct 776 ms 1656 KB Output is correct
12 Correct 1088 ms 3056 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 708 KB Output is correct
2 Correct 81 ms 668 KB Output is correct
3 Correct 107 ms 788 KB Output is correct
4 Correct 82 ms 704 KB Output is correct
5 Correct 1022 ms 2988 KB Output is correct
6 Correct 999 ms 2492 KB Output is correct
7 Correct 1018 ms 2952 KB Output is correct
8 Correct 983 ms 3408 KB Output is correct
9 Correct 965 ms 3356 KB Output is correct
10 Correct 917 ms 2792 KB Output is correct
11 Correct 203 ms 896 KB Output is correct
12 Correct 913 ms 3012 KB Output is correct
13 Correct 854 ms 2580 KB Output is correct
14 Correct 578 ms 1728 KB Output is correct
15 Correct 515 ms 1712 KB Output is correct
16 Correct 402 ms 1308 KB Output is correct
17 Correct 946 ms 2276 KB Output is correct
18 Correct 924 ms 2272 KB Output is correct
19 Correct 922 ms 2460 KB Output is correct
20 Correct 927 ms 2200 KB Output is correct
21 Correct 236 ms 980 KB Output is correct
22 Correct 678 ms 2060 KB Output is correct
23 Correct 798 ms 2408 KB Output is correct
24 Correct 700 ms 1916 KB Output is correct
25 Correct 96 ms 720 KB Output is correct
26 Correct 84 ms 656 KB Output is correct
27 Correct 90 ms 712 KB Output is correct
28 Correct 85 ms 708 KB Output is correct
29 Correct 839 ms 2440 KB Output is correct
30 Correct 846 ms 2308 KB Output is correct
31 Correct 951 ms 3540 KB Output is correct
32 Correct 931 ms 2656 KB Output is correct
33 Correct 866 ms 2620 KB Output is correct
34 Correct 506 ms 1496 KB Output is correct
35 Correct 803 ms 2108 KB Output is correct
36 Correct 916 ms 2604 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 628 KB Output is correct
2 Correct 102 ms 816 KB Output is correct
3 Correct 98 ms 764 KB Output is correct
4 Correct 109 ms 744 KB Output is correct
5 Correct 1106 ms 3144 KB Output is correct
6 Correct 568 ms 1544 KB Output is correct
7 Correct 1150 ms 3304 KB Output is correct
8 Correct 715 ms 1608 KB Output is correct
9 Correct 712 ms 2068 KB Output is correct
10 Correct 1010 ms 3224 KB Output is correct
11 Correct 394 ms 1348 KB Output is correct
12 Correct 1016 ms 3956 KB Output is correct
13 Correct 907 ms 2732 KB Output is correct
14 Correct 672 ms 1988 KB Output is correct
15 Correct 994 ms 3512 KB Output is correct
16 Correct 966 ms 2764 KB Output is correct
17 Correct 1072 ms 2428 KB Output is correct
18 Correct 1101 ms 2528 KB Output is correct
19 Correct 1048 ms 2504 KB Output is correct
20 Correct 1041 ms 2420 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 5 ms 332 KB Output is correct
4 Correct 5 ms 332 KB Output is correct
5 Correct 7 ms 512 KB Output is correct
6 Correct 8 ms 508 KB Output is correct
7 Correct 8 ms 412 KB Output is correct
8 Correct 7 ms 480 KB Output is correct
9 Correct 7 ms 460 KB Output is correct
10 Correct 4 ms 460 KB Output is correct
11 Correct 11 ms 460 KB Output is correct
12 Correct 14 ms 476 KB Output is correct
13 Correct 5 ms 460 KB Output is correct
14 Correct 7 ms 460 KB Output is correct
15 Correct 7 ms 356 KB Output is correct
16 Correct 8 ms 368 KB Output is correct
17 Correct 12 ms 332 KB Output is correct
18 Correct 5 ms 460 KB Output is correct
19 Correct 7 ms 416 KB Output is correct
20 Correct 12 ms 440 KB Output is correct
21 Correct 1041 ms 2320 KB Output is correct
22 Correct 1020 ms 2304 KB Output is correct
23 Correct 1008 ms 2344 KB Output is correct
24 Correct 1049 ms 2364 KB Output is correct
25 Correct 985 ms 3392 KB Output is correct
26 Correct 966 ms 3572 KB Output is correct
27 Correct 1026 ms 2436 KB Output is correct
28 Correct 1016 ms 2228 KB Output is correct
29 Correct 1018 ms 2488 KB Output is correct
30 Correct 651 ms 1364 KB Output is correct
31 Correct 776 ms 1656 KB Output is correct
32 Correct 1088 ms 3056 KB Output is correct
33 Correct 98 ms 628 KB Output is correct
34 Correct 102 ms 816 KB Output is correct
35 Correct 98 ms 764 KB Output is correct
36 Correct 109 ms 744 KB Output is correct
37 Correct 1106 ms 3144 KB Output is correct
38 Correct 568 ms 1544 KB Output is correct
39 Correct 1150 ms 3304 KB Output is correct
40 Correct 715 ms 1608 KB Output is correct
41 Correct 712 ms 2068 KB Output is correct
42 Correct 1010 ms 3224 KB Output is correct
43 Correct 394 ms 1348 KB Output is correct
44 Correct 1016 ms 3956 KB Output is correct
45 Correct 907 ms 2732 KB Output is correct
46 Correct 672 ms 1988 KB Output is correct
47 Correct 994 ms 3512 KB Output is correct
48 Correct 966 ms 2764 KB Output is correct
49 Correct 1072 ms 2428 KB Output is correct
50 Correct 1101 ms 2528 KB Output is correct
51 Correct 1048 ms 2504 KB Output is correct
52 Correct 1041 ms 2420 KB Output is correct
53 Correct 113 ms 988 KB Output is correct
54 Correct 112 ms 1004 KB Output is correct
55 Correct 103 ms 916 KB Output is correct
56 Correct 101 ms 944 KB Output is correct
57 Correct 859 ms 2224 KB Output is correct
58 Correct 477 ms 1420 KB Output is correct
59 Correct 1118 ms 3040 KB Output is correct
60 Correct 445 ms 1304 KB Output is correct
61 Correct 926 ms 2732 KB Output is correct
62 Correct 992 ms 3552 KB Output is correct
63 Correct 992 ms 3688 KB Output is correct
64 Correct 1045 ms 3552 KB Output is correct
65 Correct 532 ms 1616 KB Output is correct
66 Correct 445 ms 1484 KB Output is correct
67 Correct 1010 ms 2840 KB Output is correct
68 Correct 895 ms 2596 KB Output is correct
69 Correct 1181 ms 2648 KB Output is correct
70 Correct 1121 ms 2648 KB Output is correct
71 Correct 1113 ms 2620 KB Output is correct
72 Correct 1128 ms 2664 KB Output is correct
73 Correct 595 ms 1980 KB Output is correct
74 Correct 894 ms 2548 KB Output is correct
75 Correct 1044 ms 3948 KB Output is correct
76 Correct 1030 ms 3896 KB Output is correct
77 Correct 113 ms 1040 KB Output is correct
78 Correct 106 ms 1060 KB Output is correct
79 Correct 115 ms 1092 KB Output is correct
80 Correct 119 ms 1024 KB Output is correct
81 Correct 853 ms 2556 KB Output is correct
82 Correct 632 ms 1844 KB Output is correct
83 Correct 418 ms 1516 KB Output is correct
84 Correct 881 ms 2584 KB Output is correct
85 Correct 1022 ms 3016 KB Output is correct
86 Correct 1004 ms 3396 KB Output is correct
87 Correct 749 ms 2124 KB Output is correct
88 Correct 420 ms 1524 KB Output is correct

Subtask #6
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 5 ms 332 KB Output is correct
4 Correct 5 ms 332 KB Output is correct
5 Correct 7 ms 512 KB Output is correct
6 Correct 8 ms 508 KB Output is correct
7 Correct 8 ms 412 KB Output is correct
8 Correct 7 ms 480 KB Output is correct
9 Correct 7 ms 460 KB Output is correct
10 Correct 4 ms 460 KB Output is correct
11 Correct 11 ms 460 KB Output is correct
12 Correct 14 ms 476 KB Output is correct
13 Correct 5 ms 460 KB Output is correct
14 Correct 7 ms 460 KB Output is correct
15 Correct 7 ms 356 KB Output is correct
16 Correct 8 ms 368 KB Output is correct
17 Correct 12 ms 332 KB Output is correct
18 Correct 5 ms 460 KB Output is correct
19 Correct 7 ms 416 KB Output is correct
20 Correct 12 ms 440 KB Output is correct
21 Correct 1041 ms 2320 KB Output is correct
22 Correct 1020 ms 2304 KB Output is correct
23 Correct 1008 ms 2344 KB Output is correct
24 Correct 1049 ms 2364 KB Output is correct
25 Correct 985 ms 3392 KB Output is correct
26 Correct 966 ms 3572 KB Output is correct
27 Correct 1026 ms 2436 KB Output is correct
28 Correct 1016 ms 2228 KB Output is correct
29 Correct 1018 ms 2488 KB Output is correct
30 Correct 651 ms 1364 KB Output is correct
31 Correct 776 ms 1656 KB Output is correct
32 Correct 1088 ms 3056 KB Output is correct
33 Correct 91 ms 708 KB Output is correct
34 Correct 81 ms 668 KB Output is correct
35 Correct 107 ms 788 KB Output is correct
36 Correct 82 ms 704 KB Output is correct
37 Correct 1022 ms 2988 KB Output is correct
38 Correct 999 ms 2492 KB Output is correct
39 Correct 1018 ms 2952 KB Output is correct
40 Correct 983 ms 3408 KB Output is correct
41 Correct 965 ms 3356 KB Output is correct
42 Correct 917 ms 2792 KB Output is correct
43 Correct 203 ms 896 KB Output is correct
44 Correct 913 ms 3012 KB Output is correct
45 Correct 854 ms 2580 KB Output is correct
46 Correct 578 ms 1728 KB Output is correct
47 Correct 515 ms 1712 KB Output is correct
48 Correct 402 ms 1308 KB Output is correct
49 Correct 946 ms 2276 KB Output is correct
50 Correct 924 ms 2272 KB Output is correct
51 Correct 922 ms 2460 KB Output is correct
52 Correct 927 ms 2200 KB Output is correct
53 Correct 236 ms 980 KB Output is correct
54 Correct 678 ms 2060 KB Output is correct
55 Correct 798 ms 2408 KB Output is correct
56 Correct 700 ms 1916 KB Output is correct
57 Correct 96 ms 720 KB Output is correct
58 Correct 84 ms 656 KB Output is correct
59 Correct 90 ms 712 KB Output is correct
60 Correct 85 ms 708 KB Output is correct
61 Correct 839 ms 2440 KB Output is correct
62 Correct 846 ms 2308 KB Output is correct
63 Correct 951 ms 3540 KB Output is correct
64 Correct 931 ms 2656 KB Output is correct
65 Correct 866 ms 2620 KB Output is correct
66 Correct 506 ms 1496 KB Output is correct
67 Correct 803 ms 2108 KB Output is correct
68 Correct 916 ms 2604 KB Output is correct
69 Correct 98 ms 628 KB Output is correct
70 Correct 102 ms 816 KB Output is correct
71 Correct 98 ms 764 KB Output is correct
72 Correct 109 ms 744 KB Output is correct
73 Correct 1106 ms 3144 KB Output is correct
74 Correct 568 ms 1544 KB Output is correct
75 Correct 1150 ms 3304 KB Output is correct
76 Correct 715 ms 1608 KB Output is correct
77 Correct 712 ms 2068 KB Output is correct
78 Correct 1010 ms 3224 KB Output is correct
79 Correct 394 ms 1348 KB Output is correct
80 Correct 1016 ms 3956 KB Output is correct
81 Correct 907 ms 2732 KB Output is correct
82 Correct 672 ms 1988 KB Output is correct
83 Correct 994 ms 3512 KB Output is correct
84 Correct 966 ms 2764 KB Output is correct
85 Correct 1072 ms 2428 KB Output is correct
86 Correct 1101 ms 2528 KB Output is correct
87 Correct 1048 ms 2504 KB Output is correct
88 Correct 1041 ms 2420 KB Output is correct
89 Correct 113 ms 988 KB Output is correct
90 Correct 112 ms 1004 KB Output is correct
91 Correct 103 ms 916 KB Output is correct
92 Correct 101 ms 944 KB Output is correct
93 Correct 859 ms 2224 KB Output is correct
94 Correct 477 ms 1420 KB Output is correct
95 Correct 1118 ms 3040 KB Output is correct
96 Correct 445 ms 1304 KB Output is correct
97 Correct 926 ms 2732 KB Output is correct
98 Correct 992 ms 3552 KB Output is correct
99 Correct 992 ms 3688 KB Output is correct
100 Correct 1045 ms 3552 KB Output is correct
101 Correct 532 ms 1616 KB Output is correct
102 Correct 445 ms 1484 KB Output is correct
103 Correct 1010 ms 2840 KB Output is correct
104 Correct 895 ms 2596 KB Output is correct
105 Correct 1181 ms 2648 KB Output is correct
106 Correct 1121 ms 2648 KB Output is correct
107 Correct 1113 ms 2620 KB Output is correct
108 Correct 1128 ms 2664 KB Output is correct
109 Correct 595 ms 1980 KB Output is correct
110 Correct 894 ms 2548 KB Output is correct
111 Correct 1044 ms 3948 KB Output is correct
112 Correct 1030 ms 3896 KB Output is correct
113 Correct 113 ms 1040 KB Output is correct
114 Correct 106 ms 1060 KB Output is correct
115 Correct 115 ms 1092 KB Output is correct
116 Correct 119 ms 1024 KB Output is correct
117 Correct 853 ms 2556 KB Output is correct
118 Correct 632 ms 1844 KB Output is correct
119 Correct 418 ms 1516 KB Output is correct
120 Correct 881 ms 2584 KB Output is correct
121 Correct 1022 ms 3016 KB Output is correct
122 Correct 1004 ms 3396 KB Output is correct
123 Correct 749 ms 2124 KB Output is correct
124 Correct 420 ms 1524 KB Output is correct
125 Correct 242 ms 1464 KB Output is correct
126 Correct 242 ms 1448 KB Output is correct
127 Correct 322 ms 1520 KB Output is correct
128 Correct 243 ms 1420 KB Output is correct
129 Correct 244 ms 1476 KB Output is correct
130 Correct 244 ms 1520 KB Output is correct
131 Correct 1550 ms 2268 KB Output is correct
132 Correct 3966 ms 4176 KB Output is correct
133 Correct 4620 ms 5668 KB Output is correct
134 Correct 2152 ms 2544 KB Output is correct
135 Correct 4645 ms 5640 KB Output is correct
136 Correct 718 ms 7568 KB Output is correct
137 Correct 4271 ms 10748 KB Output is correct
138 Correct 3641 ms 8640 KB Output is correct
139 Correct 4155 ms 9656 KB Output is correct
140 Correct 4318 ms 10344 KB Output is correct
141 Correct 3978 ms 9176 KB Output is correct
142 Correct 855 ms 5724 KB Output is correct
143 Correct 1791 ms 6540 KB Output is correct
144 Correct 583 ms 5520 KB Output is correct
145 Correct 4171 ms 10196 KB Output is correct
146 Correct 2727 ms 7432 KB Output is correct
147 Correct 1858 ms 6540 KB Output is correct
148 Correct 1731 ms 6528 KB Output is correct
149 Correct 4280 ms 9480 KB Output is correct
150 Correct 4249 ms 9504 KB Output is correct
151 Correct 4160 ms 9624 KB Output is correct
152 Correct 4181 ms 9516 KB Output is correct
153 Correct 4220 ms 9552 KB Output is correct
154 Correct 4190 ms 9564 KB Output is correct
155 Correct 1236 ms 6096 KB Output is correct
156 Correct 2045 ms 6876 KB Output is correct
157 Correct 4258 ms 10428 KB Output is correct
158 Correct 4215 ms 10516 KB Output is correct
159 Correct 3852 ms 8828 KB Output is correct
160 Correct 2899 ms 7608 KB Output is correct
161 Correct 317 ms 5212 KB Output is correct
162 Correct 295 ms 5188 KB Output is correct
163 Correct 246 ms 5188 KB Output is correct
164 Correct 353 ms 5268 KB Output is correct
165 Correct 252 ms 5316 KB Output is correct
166 Correct 236 ms 5264 KB Output is correct
167 Correct 4261 ms 10868 KB Output is correct
168 Correct 4260 ms 10904 KB Output is correct
169 Correct 4194 ms 10428 KB Output is correct
170 Correct 4175 ms 10128 KB Output is correct
171 Correct 3904 ms 9280 KB Output is correct
172 Correct 2481 ms 7220 KB Output is correct
173 Correct 4245 ms 10392 KB Output is correct
174 Correct 2612 ms 7352 KB Output is correct
175 Correct 3989 ms 9368 KB Output is correct
176 Correct 1661 ms 6464 KB Output is correct
177 Correct 3719 ms 8724 KB Output is correct
178 Correct 3636 ms 8388 KB Output is correct