oj.uz

Submission #572597

# Submission time Handle Problem Language Result Execution time Memory
572597 2022-06-04T18:33:27 Z vovamr Segments (IZhO18_segments) C++17
75 / 100
 5000 ms 26112 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) 	(x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }

constexpr int N = 2e5 + 100;
constexpr int b = 2100;

int n;
ve<pii> segs;
ve<int> s[N / b], st[N / b];
inline void reset(const set<pii> &bodek) {
	for (int i = 0; i <= (n - 1) / b; ++i) s[i].clear(), st[i].clear();
	n = sz(bodek); int ptr = 0; segs.clear(); segs.resize(n);
	for (auto &[r, l] : bodek) segs[ptr++] = {r, l};
	for (int i = 0; i < n; ++i) { auto &[r, l] = segs[i]; s[i / b].pb(l), st[i / b].pb(-(r - l + 1)); }
	for (int i = 0; i <= (n - 1) / b; ++i) sort(all(s[i])), sort(all(st[i]));
}
inline void debug() {
	cout << "segments:" << '\n';
	for (int i = 0; i < n; ++i) {
		auto &[r, l] = segs[i];
		cout << l << " " << r << '\n';
	}
	for (int i = 0; i <= (n - 1) / b; ++i) {
		cout << "block " << i << ": ";
		for (auto &le : s[i]) cout << le << " ";
		cout << '\n';
	}
	cout << '\n';
}
inline int cnts(int id, int x) { return upper_bound(all(s[id]), x) - s[id].begin(); }
inline int cnts1(int id, int x) { return upper_bound(all(st[id]), x) - st[id].begin(); }
inline int get1(int pos, int x) {
	int ans = 0;
	pos = lower_bound(all(segs), mpp(pos, -1)) - segs.begin();
	if (pos == sz(segs)) return 0;
	int bl = pos / b;
	for (int i = bl + 1; i <= (n - 1) / b; ++i) ans += cnts(i, x);
	for (int i = pos; i < min(n, (bl + 1) * b); ++i) ans += segs[i].se <= x;
	return ans;
}
inline int get2(int l, int r, int x) {
	l = lower_bound(all(segs), mpp(l, -1)) - segs.begin();
	r = upper_bound(all(segs), mpp(r, INT_MAX)) - segs.begin() - 1;
	if (l > r) return 0;
	int lb = l / b, rb = r / b;
	if (lb == rb) {
		int ans = 0;
		for (int i = l; i <= r; ++i) {
			ans += (segs[i].fi - segs[i].se + 1 >= x);
		} return ans;
	}
	int ans = 0;
	for (int i = lb + 1; i <= rb - 1; ++i) ans += cnts1(i, -x);
	for (int i = l; i < (lb + 1) * b; ++i) ans += (segs[i].fi - segs[i].se + 1 >= x);
	for (int i = r; i >= rb * b; --i) ans += (segs[i].fi - segs[i].se + 1 >= x);
	return ans;
}
inline int answer(int l, int r, int k) {
	if (r - l + 1 < k) return 0;
	int ans = 0;
	ans += get1(r + 1, r - k + 1);
	ans += get2(l + k - 1, r, k);
	return ans;
}

inline int isec(int l, int r, int l1, int r1) {
	return max(0, min(r, r1) - max(l, l1) + 1);
}

inline void solve() {
	int q, t;
	cin >> q >> t;

	int ID = 0;
	ve<int> tr(q);
	ve<array<int,4>> que(q);
	for (int i = 0; i < q; ++i) {
		int e;
		cin >> e;
		que[i][0] = e;
		if (e == 1) cin >> que[i][1] >> que[i][2], tr[ID++] = i;
		else if (e == 2) cin >> que[i][1], --que[i][1];
		else cin >> que[i][1] >> que[i][2] >> que[i][3];
	}

	int last = 0;
	ve<int> del(q), gdel(q);
	for (int l = 0; l < q; l += b) {
		set<pii> sgs;
		int r = min(q - 1, l + b - 1);

		fill(all(del), 0);
		for (int i = 0; i <= r; ++i) if (que[i][0] == 2) del[tr[que[i][1]]] = 1;
		for (int i = 0; i < l; ++i) if (que[i][0] == 1) {
			if (!del[i]) {
				auto &[_, l, r, __] = que[i];
				sgs.insert({r, l});
			}
		}

		reset(sgs);
		for (int i = l; i <= r; ++i) {
			auto &[e, le, re, k] = que[i];
			if (e == 1 || e == 3) {
				le ^= (t * last), re ^= (t * last);
				if (le > re) swap(le, re);
			}

			if (e == 3) {
				int ans = answer(le, re, k);
				for (int j = l; j <= r; ++j) {
					auto &[E, L, R, K] = que[j];
					if (E == 1 && !del[j] && j < i) ans += isec(le, re, L, R) >= k;
					else if (E == 2) { int J = tr[L];
						if (J < i && !gdel[J]) ans += isec(le, re, que[J][1], que[J][2]) >= k;
					}
				}
				cout << (last = ans) << '\n';
//				debug();
			}
			else if (e == 2) gdel[tr[le]] = 1;
		}
	}
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int q = 1; // cin >> q;
	while (q--) solve();
	cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 11 ms 464 KB Output is correct
4 Correct 10 ms 564 KB Output is correct
5 Correct 7 ms 800 KB Output is correct
6 Correct 7 ms 852 KB Output is correct
7 Correct 11 ms 596 KB Output is correct
8 Correct 7 ms 724 KB Output is correct
9 Correct 8 ms 724 KB Output is correct
10 Correct 4 ms 852 KB Output is correct
11 Correct 11 ms 724 KB Output is correct
12 Correct 12 ms 724 KB Output is correct
13 Correct 4 ms 724 KB Output is correct
14 Correct 8 ms 684 KB Output is correct
15 Correct 10 ms 468 KB Output is correct
16 Correct 12 ms 468 KB Output is correct
17 Correct 10 ms 596 KB Output is correct
18 Correct 5 ms 724 KB Output is correct
19 Correct 9 ms 596 KB Output is correct
20 Correct 9 ms 800 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 955 ms 9568 KB Output is correct
2 Correct 950 ms 9400 KB Output is correct
3 Correct 932 ms 9500 KB Output is correct
4 Correct 1000 ms 9800 KB Output is correct
5 Correct 962 ms 12380 KB Output is correct
6 Correct 966 ms 12576 KB Output is correct
7 Correct 926 ms 9544 KB Output is correct
8 Correct 924 ms 9392 KB Output is correct
9 Correct 919 ms 9512 KB Output is correct
10 Correct 624 ms 7760 KB Output is correct
11 Correct 726 ms 8192 KB Output is correct
12 Correct 1020 ms 10768 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 5204 KB Output is correct
2 Correct 232 ms 4940 KB Output is correct
3 Correct 244 ms 5104 KB Output is correct
4 Correct 236 ms 5008 KB Output is correct
5 Correct 1018 ms 10688 KB Output is correct
6 Correct 985 ms 9880 KB Output is correct
7 Correct 1020 ms 10288 KB Output is correct
8 Correct 976 ms 12312 KB Output is correct
9 Correct 978 ms 12076 KB Output is correct
10 Correct 931 ms 10136 KB Output is correct
11 Correct 333 ms 5396 KB Output is correct
12 Correct 936 ms 10308 KB Output is correct
13 Correct 895 ms 9360 KB Output is correct
14 Correct 661 ms 7684 KB Output is correct
15 Correct 613 ms 7092 KB Output is correct
16 Correct 508 ms 6476 KB Output is correct
17 Correct 940 ms 9180 KB Output is correct
18 Correct 934 ms 9164 KB Output is correct
19 Correct 949 ms 9288 KB Output is correct
20 Correct 942 ms 9384 KB Output is correct
21 Correct 363 ms 5556 KB Output is correct
22 Correct 736 ms 8560 KB Output is correct
23 Correct 833 ms 9436 KB Output is correct
24 Correct 768 ms 8576 KB Output is correct
25 Correct 242 ms 4940 KB Output is correct
26 Correct 231 ms 4984 KB Output is correct
27 Correct 238 ms 5008 KB Output is correct
28 Correct 231 ms 5028 KB Output is correct
29 Correct 877 ms 10020 KB Output is correct
30 Correct 870 ms 10116 KB Output is correct
31 Correct 962 ms 12008 KB Output is correct
32 Correct 930 ms 10176 KB Output is correct
33 Correct 897 ms 10528 KB Output is correct
34 Correct 591 ms 7196 KB Output is correct
35 Correct 831 ms 9420 KB Output is correct
36 Correct 911 ms 9780 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 5216 KB Output is correct
2 Correct 243 ms 5220 KB Output is correct
3 Correct 236 ms 5244 KB Output is correct
4 Correct 238 ms 5272 KB Output is correct
5 Correct 1040 ms 11228 KB Output is correct
6 Correct 541 ms 7640 KB Output is correct
7 Correct 1018 ms 11604 KB Output is correct
8 Correct 639 ms 7744 KB Output is correct
9 Correct 723 ms 8420 KB Output is correct
10 Correct 1028 ms 10600 KB Output is correct
11 Correct 450 ms 6492 KB Output is correct
12 Correct 959 ms 12292 KB Output is correct
13 Correct 878 ms 9988 KB Output is correct
14 Correct 687 ms 8160 KB Output is correct
15 Correct 967 ms 12492 KB Output is correct
16 Correct 900 ms 10448 KB Output is correct
17 Correct 924 ms 9496 KB Output is correct
18 Correct 943 ms 9508 KB Output is correct
19 Correct 925 ms 9524 KB Output is correct
20 Correct 932 ms 9536 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 11 ms 464 KB Output is correct
4 Correct 10 ms 564 KB Output is correct
5 Correct 7 ms 800 KB Output is correct
6 Correct 7 ms 852 KB Output is correct
7 Correct 11 ms 596 KB Output is correct
8 Correct 7 ms 724 KB Output is correct
9 Correct 8 ms 724 KB Output is correct
10 Correct 4 ms 852 KB Output is correct
11 Correct 11 ms 724 KB Output is correct
12 Correct 12 ms 724 KB Output is correct
13 Correct 4 ms 724 KB Output is correct
14 Correct 8 ms 684 KB Output is correct
15 Correct 10 ms 468 KB Output is correct
16 Correct 12 ms 468 KB Output is correct
17 Correct 10 ms 596 KB Output is correct
18 Correct 5 ms 724 KB Output is correct
19 Correct 9 ms 596 KB Output is correct
20 Correct 9 ms 800 KB Output is correct
21 Correct 955 ms 9568 KB Output is correct
22 Correct 950 ms 9400 KB Output is correct
23 Correct 932 ms 9500 KB Output is correct
24 Correct 1000 ms 9800 KB Output is correct
25 Correct 962 ms 12380 KB Output is correct
26 Correct 966 ms 12576 KB Output is correct
27 Correct 926 ms 9544 KB Output is correct
28 Correct 924 ms 9392 KB Output is correct
29 Correct 919 ms 9512 KB Output is correct
30 Correct 624 ms 7760 KB Output is correct
31 Correct 726 ms 8192 KB Output is correct
32 Correct 1020 ms 10768 KB Output is correct
33 Correct 233 ms 5216 KB Output is correct
34 Correct 243 ms 5220 KB Output is correct
35 Correct 236 ms 5244 KB Output is correct
36 Correct 238 ms 5272 KB Output is correct
37 Correct 1040 ms 11228 KB Output is correct
38 Correct 541 ms 7640 KB Output is correct
39 Correct 1018 ms 11604 KB Output is correct
40 Correct 639 ms 7744 KB Output is correct
41 Correct 723 ms 8420 KB Output is correct
42 Correct 1028 ms 10600 KB Output is correct
43 Correct 450 ms 6492 KB Output is correct
44 Correct 959 ms 12292 KB Output is correct
45 Correct 878 ms 9988 KB Output is correct
46 Correct 687 ms 8160 KB Output is correct
47 Correct 967 ms 12492 KB Output is correct
48 Correct 900 ms 10448 KB Output is correct
49 Correct 924 ms 9496 KB Output is correct
50 Correct 943 ms 9508 KB Output is correct
51 Correct 925 ms 9524 KB Output is correct
52 Correct 932 ms 9536 KB Output is correct
53 Correct 243 ms 5240 KB Output is correct
54 Correct 238 ms 5148 KB Output is correct
55 Correct 232 ms 5224 KB Output is correct
56 Correct 240 ms 5284 KB Output is correct
57 Correct 785 ms 8500 KB Output is correct
58 Correct 466 ms 7152 KB Output is correct
59 Correct 1002 ms 10180 KB Output is correct
60 Correct 435 ms 7172 KB Output is correct
61 Correct 888 ms 10200 KB Output is correct
62 Correct 959 ms 12408 KB Output is correct
63 Correct 954 ms 12216 KB Output is correct
64 Correct 992 ms 12396 KB Output is correct
65 Correct 531 ms 7072 KB Output is correct
66 Correct 485 ms 6768 KB Output is correct
67 Correct 963 ms 9860 KB Output is correct
68 Correct 838 ms 9344 KB Output is correct
69 Correct 925 ms 9432 KB Output is correct
70 Correct 921 ms 9520 KB Output is correct
71 Correct 937 ms 9536 KB Output is correct
72 Correct 928 ms 9500 KB Output is correct
73 Correct 589 ms 7412 KB Output is correct
74 Correct 817 ms 8684 KB Output is correct
75 Correct 949 ms 12508 KB Output is correct
76 Correct 969 ms 12288 KB Output is correct
77 Correct 238 ms 5148 KB Output is correct
78 Correct 236 ms 5352 KB Output is correct
79 Correct 233 ms 5156 KB Output is correct
80 Correct 232 ms 5240 KB Output is correct
81 Correct 816 ms 9264 KB Output is correct
82 Correct 591 ms 7364 KB Output is correct
83 Correct 446 ms 6360 KB Output is correct
84 Correct 804 ms 9416 KB Output is correct
85 Correct 952 ms 10980 KB Output is correct
86 Correct 936 ms 11192 KB Output is correct
87 Correct 710 ms 8176 KB Output is correct
88 Correct 451 ms 6232 KB Output is correct

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 11 ms 464 KB Output is correct
4 Correct 10 ms 564 KB Output is correct
5 Correct 7 ms 800 KB Output is correct
6 Correct 7 ms 852 KB Output is correct
7 Correct 11 ms 596 KB Output is correct
8 Correct 7 ms 724 KB Output is correct
9 Correct 8 ms 724 KB Output is correct
10 Correct 4 ms 852 KB Output is correct
11 Correct 11 ms 724 KB Output is correct
12 Correct 12 ms 724 KB Output is correct
13 Correct 4 ms 724 KB Output is correct
14 Correct 8 ms 684 KB Output is correct
15 Correct 10 ms 468 KB Output is correct
16 Correct 12 ms 468 KB Output is correct
17 Correct 10 ms 596 KB Output is correct
18 Correct 5 ms 724 KB Output is correct
19 Correct 9 ms 596 KB Output is correct
20 Correct 9 ms 800 KB Output is correct
21 Correct 955 ms 9568 KB Output is correct
22 Correct 950 ms 9400 KB Output is correct
23 Correct 932 ms 9500 KB Output is correct
24 Correct 1000 ms 9800 KB Output is correct
25 Correct 962 ms 12380 KB Output is correct
26 Correct 966 ms 12576 KB Output is correct
27 Correct 926 ms 9544 KB Output is correct
28 Correct 924 ms 9392 KB Output is correct
29 Correct 919 ms 9512 KB Output is correct
30 Correct 624 ms 7760 KB Output is correct
31 Correct 726 ms 8192 KB Output is correct
32 Correct 1020 ms 10768 KB Output is correct
33 Correct 244 ms 5204 KB Output is correct
34 Correct 232 ms 4940 KB Output is correct
35 Correct 244 ms 5104 KB Output is correct
36 Correct 236 ms 5008 KB Output is correct
37 Correct 1018 ms 10688 KB Output is correct
38 Correct 985 ms 9880 KB Output is correct
39 Correct 1020 ms 10288 KB Output is correct
40 Correct 976 ms 12312 KB Output is correct
41 Correct 978 ms 12076 KB Output is correct
42 Correct 931 ms 10136 KB Output is correct
43 Correct 333 ms 5396 KB Output is correct
44 Correct 936 ms 10308 KB Output is correct
45 Correct 895 ms 9360 KB Output is correct
46 Correct 661 ms 7684 KB Output is correct
47 Correct 613 ms 7092 KB Output is correct
48 Correct 508 ms 6476 KB Output is correct
49 Correct 940 ms 9180 KB Output is correct
50 Correct 934 ms 9164 KB Output is correct
51 Correct 949 ms 9288 KB Output is correct
52 Correct 942 ms 9384 KB Output is correct
53 Correct 363 ms 5556 KB Output is correct
54 Correct 736 ms 8560 KB Output is correct
55 Correct 833 ms 9436 KB Output is correct
56 Correct 768 ms 8576 KB Output is correct
57 Correct 242 ms 4940 KB Output is correct
58 Correct 231 ms 4984 KB Output is correct
59 Correct 238 ms 5008 KB Output is correct
60 Correct 231 ms 5028 KB Output is correct
61 Correct 877 ms 10020 KB Output is correct
62 Correct 870 ms 10116 KB Output is correct
63 Correct 962 ms 12008 KB Output is correct
64 Correct 930 ms 10176 KB Output is correct
65 Correct 897 ms 10528 KB Output is correct
66 Correct 591 ms 7196 KB Output is correct
67 Correct 831 ms 9420 KB Output is correct
68 Correct 911 ms 9780 KB Output is correct
69 Correct 233 ms 5216 KB Output is correct
70 Correct 243 ms 5220 KB Output is correct
71 Correct 236 ms 5244 KB Output is correct
72 Correct 238 ms 5272 KB Output is correct
73 Correct 1040 ms 11228 KB Output is correct
74 Correct 541 ms 7640 KB Output is correct
75 Correct 1018 ms 11604 KB Output is correct
76 Correct 639 ms 7744 KB Output is correct
77 Correct 723 ms 8420 KB Output is correct
78 Correct 1028 ms 10600 KB Output is correct
79 Correct 450 ms 6492 KB Output is correct
80 Correct 959 ms 12292 KB Output is correct
81 Correct 878 ms 9988 KB Output is correct
82 Correct 687 ms 8160 KB Output is correct
83 Correct 967 ms 12492 KB Output is correct
84 Correct 900 ms 10448 KB Output is correct
85 Correct 924 ms 9496 KB Output is correct
86 Correct 943 ms 9508 KB Output is correct
87 Correct 925 ms 9524 KB Output is correct
88 Correct 932 ms 9536 KB Output is correct
89 Correct 243 ms 5240 KB Output is correct
90 Correct 238 ms 5148 KB Output is correct
91 Correct 232 ms 5224 KB Output is correct
92 Correct 240 ms 5284 KB Output is correct
93 Correct 785 ms 8500 KB Output is correct
94 Correct 466 ms 7152 KB Output is correct
95 Correct 1002 ms 10180 KB Output is correct
96 Correct 435 ms 7172 KB Output is correct
97 Correct 888 ms 10200 KB Output is correct
98 Correct 959 ms 12408 KB Output is correct
99 Correct 954 ms 12216 KB Output is correct
100 Correct 992 ms 12396 KB Output is correct
101 Correct 531 ms 7072 KB Output is correct
102 Correct 485 ms 6768 KB Output is correct
103 Correct 963 ms 9860 KB Output is correct
104 Correct 838 ms 9344 KB Output is correct
105 Correct 925 ms 9432 KB Output is correct
106 Correct 921 ms 9520 KB Output is correct
107 Correct 937 ms 9536 KB Output is correct
108 Correct 928 ms 9500 KB Output is correct
109 Correct 589 ms 7412 KB Output is correct
110 Correct 817 ms 8684 KB Output is correct
111 Correct 949 ms 12508 KB Output is correct
112 Correct 969 ms 12288 KB Output is correct
113 Correct 238 ms 5148 KB Output is correct
114 Correct 236 ms 5352 KB Output is correct
115 Correct 233 ms 5156 KB Output is correct
116 Correct 232 ms 5240 KB Output is correct
117 Correct 816 ms 9264 KB Output is correct
118 Correct 591 ms 7364 KB Output is correct
119 Correct 446 ms 6360 KB Output is correct
120 Correct 804 ms 9416 KB Output is correct
121 Correct 952 ms 10980 KB Output is correct
122 Correct 936 ms 11192 KB Output is correct
123 Correct 710 ms 8176 KB Output is correct
124 Correct 451 ms 6232 KB Output is correct
125 Correct 533 ms 10332 KB Output is correct
126 Correct 518 ms 10188 KB Output is correct
127 Correct 526 ms 10296 KB Output is correct
128 Correct 524 ms 10356 KB Output is correct
129 Correct 520 ms 10156 KB Output is correct
130 Correct 531 ms 10256 KB Output is correct
131 Correct 1412 ms 14104 KB Output is correct
132 Correct 3402 ms 17956 KB Output is correct
133 Correct 4512 ms 20576 KB Output is correct
134 Correct 1857 ms 14884 KB Output is correct
135 Correct 4838 ms 21140 KB Output is correct
136 Correct 725 ms 13236 KB Output is correct
137 Correct 4991 ms 26112 KB Output is correct
138 Correct 3735 ms 19856 KB Output is correct
139 Correct 4547 ms 22940 KB Output is correct
140 Correct 4900 ms 23816 KB Output is correct
141 Correct 4081 ms 21392 KB Output is correct
142 Correct 964 ms 11208 KB Output is correct
143 Correct 1769 ms 13308 KB Output is correct
144 Correct 747 ms 10764 KB Output is correct
145 Correct 4922 ms 22368 KB Output is correct
146 Correct 2650 ms 16168 KB Output is correct
147 Correct 1836 ms 13984 KB Output is correct
148 Correct 1702 ms 13272 KB Output is correct
149 Correct 3751 ms 18624 KB Output is correct
150 Correct 3692 ms 18572 KB Output is correct
151 Correct 3699 ms 18580 KB Output is correct
152 Correct 3791 ms 18600 KB Output is correct
153 Correct 3834 ms 18628 KB Output is correct
154 Correct 3753 ms 18568 KB Output is correct
155 Correct 1272 ms 12124 KB Output is correct
156 Correct 1928 ms 14080 KB Output is correct
157 Correct 4789 ms 22760 KB Output is correct
158 Execution timed out 5065 ms 23328 KB Time limit exceeded
159 Halted 0 ms 0 KB -