oj.uz

Submission #379670

# Submission time Handle Problem Language Result Execution time Memory
379670 2021-03-19T02:16:05 Z cheissmart Segments (IZhO18_segments) C++14
100 / 100
 2395 ms 10780 KB 
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "Line(" << __LINE__ << ") -> " << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 2e5 + 7, K = 2000;

pi seg[N];
V<array<int, 3>> buf;
int alive[N], new_id = 1;
int tot = 0;
vi r_bucket[N / K + 1], l_bucket[N / K + 1];
V<array<int, 3>> all;

void rebuild() {
	if(tot) for(int i = 0; i <= (tot - 1) / K; i++)
		l_bucket[i].clear(), r_bucket[i].clear();
	tot = 0;
	all.clear();
	for(int i = 1; i < new_id; i++) if(alive[i]) {
		tot++;
		int l = seg[i].F, r = seg[i].S;
		all.PB({r - l, l, r});
	}
	sort(ALL(all));
	for(int i = 0; i < tot; i++) {
		l_bucket[i / K].PB(all[i][1]);
		r_bucket[i / K].PB(all[i][2]);
	}
	if(tot) for(int i = 0; i <= (tot - 1) / K; i++) {
		sort(ALL(l_bucket[i]));
		sort(ALL(r_bucket[i]));
	}
	buf.clear();
}

void add(int l, int r) {
	alive[new_id] = 1;
	seg[new_id] = {l, r};
	buf.PB({seg[new_id].F, seg[new_id].S, 1});
	new_id++;
	if(buf.size() > K) rebuild();
}

void del(int id) {
	alive[id] = 0;
	buf.PB({seg[id].F, seg[id].S, -1});
	if(buf.size() > K) rebuild();
}

int qry(int l, int r, int k) { // k is length
	if(r - l < k) return 0;
	int ans = tot;
	if(tot) for(int i = 0; i <= (tot - 1) / K; i++) {
		int lb = i * K, rb = min((i + 1) * K, tot);
		if(all[rb - 1][0] < k) {
			ans -= int(l_bucket[i].size());
			continue;
		}
		if(all[lb][0] >= k) {
			ans -= lower_bound(ALL(r_bucket[i]), l + k) - r_bucket[i].begin();
			ans -= int(l_bucket[i].size()) - (upper_bound(ALL(l_bucket[i]), r - k) - l_bucket[i].begin());
		} else {
			for(int j = lb; j < rb; j++) if(all[j][0] >= k) {
				if(all[j][2] < l + k) ans--;
				if(all[j][1] > r - k) ans--;
			} else {
				ans--;
			}
		}
	}
	for(auto p:buf) {
		int L = max(l, p[0]), R = min(r, p[1]);
		if(R - L >= k)
			ans += p[2];
	}
	return ans;
}

signed main()
{
	IO_OP;

	int n, t;
	cin >> n >> t;
	int ans = 0;
	for(int i = 0; i < n; i++) {
		int op;
		cin >> op;
		auto decode = [&] (int& a, int& b) {
			a ^= t * ans, b ^= t * ans;
			if(a > b) swap(a, b);
		};
		if(op == 1) {
			int a, b;
			cin >> a >> b;
			decode(a, b);
			add(a, b);
		} else if(op == 2) {
			int id;	
			cin >> id;
			del(id);
		} else {
			int a, b, k;
			cin >> a >> b >> k;
			decode(a, b);
			ans = qry(a, b, k - 1);
			cout << ans << '\n';
		}
	}
	
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 5 ms 364 KB Output is correct
4 Correct 4 ms 364 KB Output is correct
5 Correct 5 ms 492 KB Output is correct
6 Correct 9 ms 492 KB Output is correct
7 Correct 5 ms 492 KB Output is correct
8 Correct 6 ms 492 KB Output is correct
9 Correct 7 ms 492 KB Output is correct
10 Correct 4 ms 492 KB Output is correct
11 Correct 10 ms 492 KB Output is correct
12 Correct 13 ms 492 KB Output is correct
13 Correct 5 ms 492 KB Output is correct
14 Correct 7 ms 492 KB Output is correct
15 Correct 4 ms 364 KB Output is correct
16 Correct 5 ms 492 KB Output is correct
17 Correct 6 ms 492 KB Output is correct
18 Correct 4 ms 492 KB Output is correct
19 Correct 6 ms 492 KB Output is correct
20 Correct 6 ms 492 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 547 ms 2212 KB Output is correct
2 Correct 583 ms 2208 KB Output is correct
3 Correct 551 ms 2284 KB Output is correct
4 Correct 479 ms 2468 KB Output is correct
5 Correct 584 ms 3360 KB Output is correct
6 Correct 591 ms 3488 KB Output is correct
7 Correct 635 ms 2340 KB Output is correct
8 Correct 556 ms 2232 KB Output is correct
9 Correct 542 ms 2304 KB Output is correct
10 Correct 489 ms 1416 KB Output is correct
11 Correct 447 ms 1576 KB Output is correct
12 Correct 489 ms 3236 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 1004 KB Output is correct
2 Correct 101 ms 876 KB Output is correct
3 Correct 91 ms 876 KB Output is correct
4 Correct 89 ms 876 KB Output is correct
5 Correct 514 ms 3236 KB Output is correct
6 Correct 425 ms 2596 KB Output is correct
7 Correct 505 ms 2688 KB Output is correct
8 Correct 578 ms 3364 KB Output is correct
9 Correct 586 ms 3384 KB Output is correct
10 Correct 522 ms 2724 KB Output is correct
11 Correct 116 ms 1004 KB Output is correct
12 Correct 518 ms 3236 KB Output is correct
13 Correct 466 ms 2608 KB Output is correct
14 Correct 298 ms 1704 KB Output is correct
15 Correct 269 ms 1576 KB Output is correct
16 Correct 221 ms 1408 KB Output is correct
17 Correct 490 ms 2212 KB Output is correct
18 Correct 487 ms 2212 KB Output is correct
19 Correct 503 ms 2280 KB Output is correct
20 Correct 487 ms 2492 KB Output is correct
21 Correct 137 ms 1132 KB Output is correct
22 Correct 361 ms 1956 KB Output is correct
23 Correct 437 ms 2212 KB Output is correct
24 Correct 374 ms 1956 KB Output is correct
25 Correct 91 ms 1004 KB Output is correct
26 Correct 100 ms 876 KB Output is correct
27 Correct 102 ms 876 KB Output is correct
28 Correct 94 ms 920 KB Output is correct
29 Correct 468 ms 2416 KB Output is correct
30 Correct 459 ms 2340 KB Output is correct
31 Correct 579 ms 3364 KB Output is correct
32 Correct 508 ms 2724 KB Output is correct
33 Correct 474 ms 2472 KB Output is correct
34 Correct 268 ms 1588 KB Output is correct
35 Correct 414 ms 2212 KB Output is correct
36 Correct 492 ms 2596 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 876 KB Output is correct
2 Correct 95 ms 876 KB Output is correct
3 Correct 96 ms 876 KB Output is correct
4 Correct 97 ms 876 KB Output is correct
5 Correct 543 ms 3192 KB Output is correct
6 Correct 623 ms 1388 KB Output is correct
7 Correct 630 ms 3236 KB Output is correct
8 Correct 385 ms 1448 KB Output is correct
9 Correct 394 ms 1832 KB Output is correct
10 Correct 566 ms 3240 KB Output is correct
11 Correct 252 ms 1468 KB Output is correct
12 Correct 626 ms 3488 KB Output is correct
13 Correct 492 ms 2468 KB Output is correct
14 Correct 382 ms 1820 KB Output is correct
15 Correct 645 ms 3236 KB Output is correct
16 Correct 611 ms 2696 KB Output is correct
17 Correct 554 ms 2288 KB Output is correct
18 Correct 573 ms 2484 KB Output is correct
19 Correct 553 ms 2468 KB Output is correct
20 Correct 571 ms 2604 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 5 ms 364 KB Output is correct
4 Correct 4 ms 364 KB Output is correct
5 Correct 5 ms 492 KB Output is correct
6 Correct 9 ms 492 KB Output is correct
7 Correct 5 ms 492 KB Output is correct
8 Correct 6 ms 492 KB Output is correct
9 Correct 7 ms 492 KB Output is correct
10 Correct 4 ms 492 KB Output is correct
11 Correct 10 ms 492 KB Output is correct
12 Correct 13 ms 492 KB Output is correct
13 Correct 5 ms 492 KB Output is correct
14 Correct 7 ms 492 KB Output is correct
15 Correct 4 ms 364 KB Output is correct
16 Correct 5 ms 492 KB Output is correct
17 Correct 6 ms 492 KB Output is correct
18 Correct 4 ms 492 KB Output is correct
19 Correct 6 ms 492 KB Output is correct
20 Correct 6 ms 492 KB Output is correct
21 Correct 547 ms 2212 KB Output is correct
22 Correct 583 ms 2208 KB Output is correct
23 Correct 551 ms 2284 KB Output is correct
24 Correct 479 ms 2468 KB Output is correct
25 Correct 584 ms 3360 KB Output is correct
26 Correct 591 ms 3488 KB Output is correct
27 Correct 635 ms 2340 KB Output is correct
28 Correct 556 ms 2232 KB Output is correct
29 Correct 542 ms 2304 KB Output is correct
30 Correct 489 ms 1416 KB Output is correct
31 Correct 447 ms 1576 KB Output is correct
32 Correct 489 ms 3236 KB Output is correct
33 Correct 89 ms 876 KB Output is correct
34 Correct 95 ms 876 KB Output is correct
35 Correct 96 ms 876 KB Output is correct
36 Correct 97 ms 876 KB Output is correct
37 Correct 543 ms 3192 KB Output is correct
38 Correct 623 ms 1388 KB Output is correct
39 Correct 630 ms 3236 KB Output is correct
40 Correct 385 ms 1448 KB Output is correct
41 Correct 394 ms 1832 KB Output is correct
42 Correct 566 ms 3240 KB Output is correct
43 Correct 252 ms 1468 KB Output is correct
44 Correct 626 ms 3488 KB Output is correct
45 Correct 492 ms 2468 KB Output is correct
46 Correct 382 ms 1820 KB Output is correct
47 Correct 645 ms 3236 KB Output is correct
48 Correct 611 ms 2696 KB Output is correct
49 Correct 554 ms 2288 KB Output is correct
50 Correct 573 ms 2484 KB Output is correct
51 Correct 553 ms 2468 KB Output is correct
52 Correct 571 ms 2604 KB Output is correct
53 Correct 96 ms 1388 KB Output is correct
54 Correct 105 ms 1188 KB Output is correct
55 Correct 105 ms 1388 KB Output is correct
56 Correct 102 ms 1260 KB Output is correct
57 Correct 541 ms 2156 KB Output is correct
58 Correct 414 ms 1516 KB Output is correct
59 Correct 546 ms 3168 KB Output is correct
60 Correct 617 ms 1616 KB Output is correct
61 Correct 494 ms 2980 KB Output is correct
62 Correct 584 ms 3748 KB Output is correct
63 Correct 626 ms 3868 KB Output is correct
64 Correct 578 ms 3748 KB Output is correct
65 Correct 291 ms 1992 KB Output is correct
66 Correct 254 ms 1772 KB Output is correct
67 Correct 507 ms 3028 KB Output is correct
68 Correct 470 ms 2656 KB Output is correct
69 Correct 557 ms 2752 KB Output is correct
70 Correct 552 ms 2816 KB Output is correct
71 Correct 658 ms 2788 KB Output is correct
72 Correct 621 ms 2920 KB Output is correct
73 Correct 333 ms 2088 KB Output is correct
74 Correct 524 ms 2852 KB Output is correct
75 Correct 608 ms 4172 KB Output is correct
76 Correct 616 ms 3916 KB Output is correct
77 Correct 94 ms 1388 KB Output is correct
78 Correct 97 ms 1388 KB Output is correct
79 Correct 94 ms 1132 KB Output is correct
80 Correct 91 ms 1260 KB Output is correct
81 Correct 447 ms 2400 KB Output is correct
82 Correct 321 ms 1756 KB Output is correct
83 Correct 265 ms 1644 KB Output is correct
84 Correct 438 ms 2468 KB Output is correct
85 Correct 511 ms 2944 KB Output is correct
86 Correct 535 ms 3744 KB Output is correct
87 Correct 400 ms 2412 KB Output is correct
88 Correct 252 ms 1900 KB Output is correct

Subtask #6
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 5 ms 364 KB Output is correct
4 Correct 4 ms 364 KB Output is correct
5 Correct 5 ms 492 KB Output is correct
6 Correct 9 ms 492 KB Output is correct
7 Correct 5 ms 492 KB Output is correct
8 Correct 6 ms 492 KB Output is correct
9 Correct 7 ms 492 KB Output is correct
10 Correct 4 ms 492 KB Output is correct
11 Correct 10 ms 492 KB Output is correct
12 Correct 13 ms 492 KB Output is correct
13 Correct 5 ms 492 KB Output is correct
14 Correct 7 ms 492 KB Output is correct
15 Correct 4 ms 364 KB Output is correct
16 Correct 5 ms 492 KB Output is correct
17 Correct 6 ms 492 KB Output is correct
18 Correct 4 ms 492 KB Output is correct
19 Correct 6 ms 492 KB Output is correct
20 Correct 6 ms 492 KB Output is correct
21 Correct 547 ms 2212 KB Output is correct
22 Correct 583 ms 2208 KB Output is correct
23 Correct 551 ms 2284 KB Output is correct
24 Correct 479 ms 2468 KB Output is correct
25 Correct 584 ms 3360 KB Output is correct
26 Correct 591 ms 3488 KB Output is correct
27 Correct 635 ms 2340 KB Output is correct
28 Correct 556 ms 2232 KB Output is correct
29 Correct 542 ms 2304 KB Output is correct
30 Correct 489 ms 1416 KB Output is correct
31 Correct 447 ms 1576 KB Output is correct
32 Correct 489 ms 3236 KB Output is correct
33 Correct 91 ms 1004 KB Output is correct
34 Correct 101 ms 876 KB Output is correct
35 Correct 91 ms 876 KB Output is correct
36 Correct 89 ms 876 KB Output is correct
37 Correct 514 ms 3236 KB Output is correct
38 Correct 425 ms 2596 KB Output is correct
39 Correct 505 ms 2688 KB Output is correct
40 Correct 578 ms 3364 KB Output is correct
41 Correct 586 ms 3384 KB Output is correct
42 Correct 522 ms 2724 KB Output is correct
43 Correct 116 ms 1004 KB Output is correct
44 Correct 518 ms 3236 KB Output is correct
45 Correct 466 ms 2608 KB Output is correct
46 Correct 298 ms 1704 KB Output is correct
47 Correct 269 ms 1576 KB Output is correct
48 Correct 221 ms 1408 KB Output is correct
49 Correct 490 ms 2212 KB Output is correct
50 Correct 487 ms 2212 KB Output is correct
51 Correct 503 ms 2280 KB Output is correct
52 Correct 487 ms 2492 KB Output is correct
53 Correct 137 ms 1132 KB Output is correct
54 Correct 361 ms 1956 KB Output is correct
55 Correct 437 ms 2212 KB Output is correct
56 Correct 374 ms 1956 KB Output is correct
57 Correct 91 ms 1004 KB Output is correct
58 Correct 100 ms 876 KB Output is correct
59 Correct 102 ms 876 KB Output is correct
60 Correct 94 ms 920 KB Output is correct
61 Correct 468 ms 2416 KB Output is correct
62 Correct 459 ms 2340 KB Output is correct
63 Correct 579 ms 3364 KB Output is correct
64 Correct 508 ms 2724 KB Output is correct
65 Correct 474 ms 2472 KB Output is correct
66 Correct 268 ms 1588 KB Output is correct
67 Correct 414 ms 2212 KB Output is correct
68 Correct 492 ms 2596 KB Output is correct
69 Correct 89 ms 876 KB Output is correct
70 Correct 95 ms 876 KB Output is correct
71 Correct 96 ms 876 KB Output is correct
72 Correct 97 ms 876 KB Output is correct
73 Correct 543 ms 3192 KB Output is correct
74 Correct 623 ms 1388 KB Output is correct
75 Correct 630 ms 3236 KB Output is correct
76 Correct 385 ms 1448 KB Output is correct
77 Correct 394 ms 1832 KB Output is correct
78 Correct 566 ms 3240 KB Output is correct
79 Correct 252 ms 1468 KB Output is correct
80 Correct 626 ms 3488 KB Output is correct
81 Correct 492 ms 2468 KB Output is correct
82 Correct 382 ms 1820 KB Output is correct
83 Correct 645 ms 3236 KB Output is correct
84 Correct 611 ms 2696 KB Output is correct
85 Correct 554 ms 2288 KB Output is correct
86 Correct 573 ms 2484 KB Output is correct
87 Correct 553 ms 2468 KB Output is correct
88 Correct 571 ms 2604 KB Output is correct
89 Correct 96 ms 1388 KB Output is correct
90 Correct 105 ms 1188 KB Output is correct
91 Correct 105 ms 1388 KB Output is correct
92 Correct 102 ms 1260 KB Output is correct
93 Correct 541 ms 2156 KB Output is correct
94 Correct 414 ms 1516 KB Output is correct
95 Correct 546 ms 3168 KB Output is correct
96 Correct 617 ms 1616 KB Output is correct
97 Correct 494 ms 2980 KB Output is correct
98 Correct 584 ms 3748 KB Output is correct
99 Correct 626 ms 3868 KB Output is correct
100 Correct 578 ms 3748 KB Output is correct
101 Correct 291 ms 1992 KB Output is correct
102 Correct 254 ms 1772 KB Output is correct
103 Correct 507 ms 3028 KB Output is correct
104 Correct 470 ms 2656 KB Output is correct
105 Correct 557 ms 2752 KB Output is correct
106 Correct 552 ms 2816 KB Output is correct
107 Correct 658 ms 2788 KB Output is correct
108 Correct 621 ms 2920 KB Output is correct
109 Correct 333 ms 2088 KB Output is correct
110 Correct 524 ms 2852 KB Output is correct
111 Correct 608 ms 4172 KB Output is correct
112 Correct 616 ms 3916 KB Output is correct
113 Correct 94 ms 1388 KB Output is correct
114 Correct 97 ms 1388 KB Output is correct
115 Correct 94 ms 1132 KB Output is correct
116 Correct 91 ms 1260 KB Output is correct
117 Correct 447 ms 2400 KB Output is correct
118 Correct 321 ms 1756 KB Output is correct
119 Correct 265 ms 1644 KB Output is correct
120 Correct 438 ms 2468 KB Output is correct
121 Correct 511 ms 2944 KB Output is correct
122 Correct 535 ms 3744 KB Output is correct
123 Correct 400 ms 2412 KB Output is correct
124 Correct 252 ms 1900 KB Output is correct
125 Correct 198 ms 2028 KB Output is correct
126 Correct 192 ms 2028 KB Output is correct
127 Correct 212 ms 2000 KB Output is correct
128 Correct 224 ms 2156 KB Output is correct
129 Correct 185 ms 2060 KB Output is correct
130 Correct 193 ms 2028 KB Output is correct
131 Correct 1241 ms 2656 KB Output is correct
132 Correct 1550 ms 6040 KB Output is correct
133 Correct 1720 ms 10000 KB Output is correct
134 Correct 1010 ms 8360 KB Output is correct
135 Correct 1916 ms 10228 KB Output is correct
136 Correct 1016 ms 7688 KB Output is correct
137 Correct 2340 ms 10604 KB Output is correct
138 Correct 1785 ms 8616 KB Output is correct
139 Correct 2153 ms 9676 KB Output is correct
140 Correct 2395 ms 10332 KB Output is correct
141 Correct 2059 ms 9140 KB Output is correct
142 Correct 487 ms 6124 KB Output is correct
143 Correct 901 ms 6756 KB Output is correct
144 Correct 440 ms 5868 KB Output is correct
145 Correct 2319 ms 10384 KB Output is correct
146 Correct 1300 ms 7500 KB Output is correct
147 Correct 948 ms 6872 KB Output is correct
148 Correct 872 ms 6692 KB Output is correct
149 Correct 1645 ms 9492 KB Output is correct
150 Correct 1713 ms 9504 KB Output is correct
151 Correct 1746 ms 9468 KB Output is correct
152 Correct 1628 ms 9516 KB Output is correct
153 Correct 1637 ms 9556 KB Output is correct
154 Correct 1682 ms 9492 KB Output is correct
155 Correct 654 ms 6312 KB Output is correct
156 Correct 983 ms 6820 KB Output is correct
157 Correct 2282 ms 10268 KB Output is correct
158 Correct 2321 ms 10500 KB Output is correct
159 Correct 1853 ms 8944 KB Output is correct
160 Correct 1394 ms 7864 KB Output is correct
161 Correct 223 ms 5544 KB Output is correct
162 Correct 260 ms 5532 KB Output is correct
163 Correct 218 ms 5612 KB Output is correct
164 Correct 263 ms 5740 KB Output is correct
165 Correct 231 ms 5592 KB Output is correct
166 Correct 197 ms 5612 KB Output is correct
167 Correct 2386 ms 10760 KB Output is correct
168 Correct 2372 ms 10780 KB Output is correct
169 Correct 2269 ms 10268 KB Output is correct
170 Correct 2166 ms 10032 KB Output is correct
171 Correct 1975 ms 9248 KB Output is correct
172 Correct 1208 ms 7332 KB Output is correct
173 Correct 2260 ms 10396 KB Output is correct
174 Correct 1275 ms 7472 KB Output is correct
175 Correct 2031 ms 9368 KB Output is correct
176 Correct 860 ms 6820 KB Output is correct
177 Correct 1828 ms 8836 KB Output is correct
178 Correct 1694 ms 8548 KB Output is correct