oj.uz

Submission #758581

# Submission time Handle Problem Language Result Execution time Memory
758581 2023-06-14T23:29:53 Z scanhex Segments (IZhO18_segments) C++17
75 / 100
 5000 ms 50140 KB 
#include <bits/stdc++.h>

using namespace std;
using nagai = long long;

struct dss {
	vector<pair<int,int>> segs;
	void insert(int l, int r) {
		segs.push_back({l, r});
	}
	int get(int l, int r, int k) {
		if (k == 0) return segs.size();
		int res = 0;
		for (auto& x : segs) {
			int ll = max(x.first, l), rr = min(x.second, r); 
			if (rr - ll + 1 >= k)
				++res;
		}
		return res;
	}
};

const int oo = 0x3f3f3f3f;
 
struct static1d {
	vector<int> coords;
	void clear() {
		coords.clear();
	}

	void add(int c) {
		coords.push_back(c);
	}

	void finalize() {
	}

	int get(int l, int r) {
		if (l > r) return 0;
		auto itr = upper_bound(coords.begin(), coords.end(), r);
		auto itl = lower_bound(coords.begin(), coords.end(), l);
		//cerr << "coords\n";
		//for(auto& x : coords) 
			//cerr << x << ' ';
		//cerr << '\n';
		//cerr << l << ' ' << r << ' ' << itr - itl << '\n';
		return itr - itl;
	}
};

bool ycmp(pair<int, int> a, pair<int, int> b) {
	return a.second < b.second;
}

struct static2d {
	vector<static1d> v;
	vector<int> xs;

	void add(int x, int y) {
		for (++x; x < v.size(); x = (x | x - 1) + 1)
			v[x].add(y);
	}

	void build(vector<pair<int,int>> pts) {
		xs.clear();
		for (auto& x : v) 
			x.clear();
		for (auto& p : pts) 
			xs.push_back(p.first);
		sort(xs.begin(), xs.end());
		xs.erase(unique(xs.begin(), xs.end()), xs.end());
		v.resize(xs.size() + 1);
		for (auto p : pts) {
			add(lower_bound(xs.begin(), xs.end(), p.first) - xs.begin(), p.second);
		}
		for (int i = 0; i < v.size(); ++i) 
			v[i].finalize();
	}

	int get(int xr, int y1, int y2) {
		++xr;
		int xrr = xr;
		xr = lower_bound(xs.begin(), xs.end(), xr) - xs.begin();
		int res = 0;
		for (; xr; xr &= xr - 1) 
			res += v[xr].get(y1, y2);
		//cerr << xrr << ' ' << y1 << ' ' << y2 << ' ' << res << '\n';
		return res;
	}

	// all inclusive
	int get(int x1, int x2, int y1, int y2) {
		if (x1 > x2) return 0;
		return get(x2, y1, y2) - get(x1 - 1, y1, y2);
	}
};

const int BL = 2000;

struct rofl2d {
	vector<pair<int,int>> all;
	vector<pair<int,int>> block;
	static2d st;
	
	void insert(int x, int y) {
		block.push_back({x, y});
		if (block.size() >= BL) {
			sort(block.begin(), block.end(), ycmp);
			vector<pair<int, int>> newall(all.size() + block.size());
			merge(all.begin(), all.end(), block.begin(), block.end(), newall.begin(), ycmp);
			all = std::move(newall);
			block.clear();
			st.build(all);
		}
	}

	int get(int x1, int x2, int y1, int y2) {
		int res = st.get(x1, x2, y1, y2);
		for (auto p : block) 
			if (x1 <= p.first && p.first <= x2 && y1 <= p.second && p.second <= y2) 
				++res;
		return res;
	}
};


struct ds {
	int tot = 0;
	rofl2d rofl_l, rofl_r;
	void insert(int l, int r) {
		++tot;
		rofl_l.insert(l, r - l);
		rofl_r.insert(r, r - l);
	}
	int get(int l, int r, int k) {
		if (r - l + 1 < k) return 0;
		if (k == 0) return tot;
		int res = tot;
		//cerr << "rofl_l" << '\n';
		res -= rofl_l.get(r - k + 2, oo, k - 1, oo);
		//cerr << "rofl_r" << '\n';
		res -= rofl_r.get(0, l + k - 2, k - 1, oo);
		//cerr << "rofl_l" << '\n';
		res -= rofl_l.get(0, oo, 0, k - 2);
		return res;
	}
};

void stress() {
	int C = 5;
	for (int i = 0; i < 10000; ++i) {
		ds smart;
		dss stupid;
		stringstream ss;
		for (int i = 0; i < 10; ++i) {
			int x = rand() % C, y = rand() % C;
			if (x > y) swap(x, y);
			ss << "1 " << x << ' ' << y << '\n';
			smart.insert(x, y);
			stupid.insert(x, y);

			int a = rand() % C, b = rand() % C, k = rand() % C;
			if (a > b) swap(a, b);
			if (smart.get(a, b, k) != stupid.get(a, b, k)) {
				ss << smart.get(a, b, k) << ' ' << stupid.get(a, b, k) << '\n';
				ss << "3 " << a << ' ' << b << ' ' << k << '\n';
				cerr << ss.str();
				exit(1);
			}
		}
	}
	exit(0);
}


int main() {
	//stress();
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, t; 
	cin >> n >> t; 
	int lastans = 0;
	vector<pair<int, int>> segs;
	ds add, del;
	while (n--) {
		int tt;
		cin >> tt; 
		if (tt == 1) {
			int a, b;
			cin >> a >> b; 
			a ^= t * lastans;
			b ^= t * lastans;
			if (a > b) swap(a, b);
			segs.push_back({a, b});
			add.insert(a, b);
		}
		else if (tt == 2) {
			int id; 
			cin >> id; 
			--id;
			del.insert(segs[id].first, segs[id].second);
		}
		else {
			int a, b, k;
			cin >> a >> b >> k;
			a ^= t * lastans;
			b ^= t * lastans;
			if (a > b) swap(a, b);
			lastans = add.get(a, b, k) - del.get(a, b, k);
			cout << lastans << '\n';
		}
	}
}

Compilation message

segments.cpp: In member function 'void static2d::add(int, int)':
segments.cpp:60:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<static1d>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |   for (++x; x < v.size(); x = (x | x - 1) + 1)
      |             ~~^~~~~~~~~~
segments.cpp:60:38: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
   60 |   for (++x; x < v.size(); x = (x | x - 1) + 1)
      |                                    ~~^~~
segments.cpp: In member function 'void static2d::build(std::vector<std::pair<int, int> >)':
segments.cpp:76:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<static1d>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |   for (int i = 0; i < v.size(); ++i)
      |                   ~~^~~~~~~~~~
segments.cpp: In member function 'int static2d::get(int, int, int)':
segments.cpp:82:7: warning: unused variable 'xrr' [-Wunused-variable]
   82 |   int xrr = xr;
      |       ^~~

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 25 ms 340 KB Output is correct
4 Correct 29 ms 404 KB Output is correct
5 Correct 11 ms 1108 KB Output is correct
6 Correct 26 ms 732 KB Output is correct
7 Correct 27 ms 660 KB Output is correct
8 Correct 14 ms 724 KB Output is correct
9 Correct 13 ms 732 KB Output is correct
10 Correct 7 ms 1108 KB Output is correct
11 Correct 17 ms 728 KB Output is correct
12 Correct 20 ms 736 KB Output is correct
13 Correct 7 ms 1108 KB Output is correct
14 Correct 13 ms 724 KB Output is correct
15 Correct 26 ms 416 KB Output is correct
16 Correct 27 ms 340 KB Output is correct
17 Correct 22 ms 724 KB Output is correct
18 Correct 9 ms 1040 KB Output is correct
19 Correct 17 ms 724 KB Output is correct
20 Correct 21 ms 724 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1437 ms 11056 KB Output is correct
2 Correct 1463 ms 11752 KB Output is correct
3 Correct 1406 ms 11316 KB Output is correct
4 Correct 931 ms 13500 KB Output is correct
5 Correct 1331 ms 22228 KB Output is correct
6 Correct 1360 ms 23320 KB Output is correct
7 Correct 1568 ms 11152 KB Output is correct
8 Correct 1501 ms 11024 KB Output is correct
9 Correct 1412 ms 11328 KB Output is correct
10 Correct 1261 ms 4584 KB Output is correct
11 Correct 1095 ms 5976 KB Output is correct
12 Correct 938 ms 19664 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 833 ms 13032 KB Output is correct
2 Correct 873 ms 13372 KB Output is correct
3 Correct 830 ms 13724 KB Output is correct
4 Correct 870 ms 13528 KB Output is correct
5 Correct 1039 ms 17632 KB Output is correct
6 Correct 689 ms 14912 KB Output is correct
7 Correct 1056 ms 15424 KB Output is correct
8 Correct 1269 ms 22076 KB Output is correct
9 Correct 1231 ms 24916 KB Output is correct
10 Correct 1050 ms 19708 KB Output is correct
11 Correct 862 ms 13916 KB Output is correct
12 Correct 1075 ms 19436 KB Output is correct
13 Correct 981 ms 18676 KB Output is correct
14 Correct 769 ms 15232 KB Output is correct
15 Correct 762 ms 15376 KB Output is correct
16 Correct 790 ms 14972 KB Output is correct
17 Correct 421 ms 11940 KB Output is correct
18 Correct 1145 ms 11136 KB Output is correct
19 Correct 1185 ms 11124 KB Output is correct
20 Correct 458 ms 11304 KB Output is correct
21 Correct 912 ms 13632 KB Output is correct
22 Correct 836 ms 17216 KB Output is correct
23 Correct 905 ms 17864 KB Output is correct
24 Correct 904 ms 17504 KB Output is correct
25 Correct 848 ms 13412 KB Output is correct
26 Correct 818 ms 13032 KB Output is correct
27 Correct 871 ms 13032 KB Output is correct
28 Correct 848 ms 13048 KB Output is correct
29 Correct 933 ms 19868 KB Output is correct
30 Correct 933 ms 20192 KB Output is correct
31 Correct 1316 ms 24316 KB Output is correct
32 Correct 1056 ms 20100 KB Output is correct
33 Correct 904 ms 18804 KB Output is correct
34 Correct 728 ms 14828 KB Output is correct
35 Correct 849 ms 16712 KB Output is correct
36 Correct 913 ms 19256 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1047 ms 13276 KB Output is correct
2 Correct 1031 ms 13308 KB Output is correct
3 Correct 1000 ms 13132 KB Output is correct
4 Correct 1033 ms 13520 KB Output is correct
5 Correct 1100 ms 19472 KB Output is correct
6 Correct 1534 ms 3060 KB Output is correct
7 Correct 1181 ms 20360 KB Output is correct
8 Correct 802 ms 4848 KB Output is correct
9 Correct 1062 ms 17124 KB Output is correct
10 Correct 1201 ms 19780 KB Output is correct
11 Correct 1072 ms 14504 KB Output is correct
12 Correct 1272 ms 21540 KB Output is correct
13 Correct 981 ms 18256 KB Output is correct
14 Correct 979 ms 15752 KB Output is correct
15 Correct 1277 ms 19196 KB Output is correct
16 Correct 989 ms 19080 KB Output is correct
17 Correct 1457 ms 12380 KB Output is correct
18 Correct 1317 ms 11936 KB Output is correct
19 Correct 1363 ms 11748 KB Output is correct
20 Correct 1461 ms 11580 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 25 ms 340 KB Output is correct
4 Correct 29 ms 404 KB Output is correct
5 Correct 11 ms 1108 KB Output is correct
6 Correct 26 ms 732 KB Output is correct
7 Correct 27 ms 660 KB Output is correct
8 Correct 14 ms 724 KB Output is correct
9 Correct 13 ms 732 KB Output is correct
10 Correct 7 ms 1108 KB Output is correct
11 Correct 17 ms 728 KB Output is correct
12 Correct 20 ms 736 KB Output is correct
13 Correct 7 ms 1108 KB Output is correct
14 Correct 13 ms 724 KB Output is correct
15 Correct 26 ms 416 KB Output is correct
16 Correct 27 ms 340 KB Output is correct
17 Correct 22 ms 724 KB Output is correct
18 Correct 9 ms 1040 KB Output is correct
19 Correct 17 ms 724 KB Output is correct
20 Correct 21 ms 724 KB Output is correct
21 Correct 1437 ms 11056 KB Output is correct
22 Correct 1463 ms 11752 KB Output is correct
23 Correct 1406 ms 11316 KB Output is correct
24 Correct 931 ms 13500 KB Output is correct
25 Correct 1331 ms 22228 KB Output is correct
26 Correct 1360 ms 23320 KB Output is correct
27 Correct 1568 ms 11152 KB Output is correct
28 Correct 1501 ms 11024 KB Output is correct
29 Correct 1412 ms 11328 KB Output is correct
30 Correct 1261 ms 4584 KB Output is correct
31 Correct 1095 ms 5976 KB Output is correct
32 Correct 938 ms 19664 KB Output is correct
33 Correct 1047 ms 13276 KB Output is correct
34 Correct 1031 ms 13308 KB Output is correct
35 Correct 1000 ms 13132 KB Output is correct
36 Correct 1033 ms 13520 KB Output is correct
37 Correct 1100 ms 19472 KB Output is correct
38 Correct 1534 ms 3060 KB Output is correct
39 Correct 1181 ms 20360 KB Output is correct
40 Correct 802 ms 4848 KB Output is correct
41 Correct 1062 ms 17124 KB Output is correct
42 Correct 1201 ms 19780 KB Output is correct
43 Correct 1072 ms 14504 KB Output is correct
44 Correct 1272 ms 21540 KB Output is correct
45 Correct 981 ms 18256 KB Output is correct
46 Correct 979 ms 15752 KB Output is correct
47 Correct 1277 ms 19196 KB Output is correct
48 Correct 989 ms 19080 KB Output is correct
49 Correct 1457 ms 12380 KB Output is correct
50 Correct 1317 ms 11936 KB Output is correct
51 Correct 1363 ms 11748 KB Output is correct
52 Correct 1461 ms 11580 KB Output is correct
53 Correct 1030 ms 13032 KB Output is correct
54 Correct 1033 ms 13092 KB Output is correct
55 Correct 1070 ms 13300 KB Output is correct
56 Correct 1028 ms 13372 KB Output is correct
57 Correct 1475 ms 7044 KB Output is correct
58 Correct 1126 ms 2380 KB Output is correct
59 Correct 1066 ms 15052 KB Output is correct
60 Correct 1493 ms 2000 KB Output is correct
61 Correct 1055 ms 19184 KB Output is correct
62 Correct 1327 ms 22536 KB Output is correct
63 Correct 1298 ms 21304 KB Output is correct
64 Correct 1280 ms 22396 KB Output is correct
65 Correct 934 ms 14512 KB Output is correct
66 Correct 917 ms 14588 KB Output is correct
67 Correct 1038 ms 18456 KB Output is correct
68 Correct 942 ms 16788 KB Output is correct
69 Correct 1355 ms 11184 KB Output is correct
70 Correct 1371 ms 11132 KB Output is correct
71 Correct 1377 ms 11424 KB Output is correct
72 Correct 1279 ms 11124 KB Output is correct
73 Correct 991 ms 15020 KB Output is correct
74 Correct 1083 ms 16888 KB Output is correct
75 Correct 1450 ms 24656 KB Output is correct
76 Correct 1339 ms 22768 KB Output is correct
77 Correct 1146 ms 13416 KB Output is correct
78 Correct 1010 ms 13472 KB Output is correct
79 Correct 1110 ms 13008 KB Output is correct
80 Correct 1000 ms 12932 KB Output is correct
81 Correct 933 ms 17928 KB Output is correct
82 Correct 913 ms 15420 KB Output is correct
83 Correct 983 ms 14376 KB Output is correct
84 Correct 1049 ms 17748 KB Output is correct
85 Correct 1081 ms 18356 KB Output is correct
86 Correct 1201 ms 19540 KB Output is correct
87 Correct 896 ms 16276 KB Output is correct
88 Correct 895 ms 14000 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 25 ms 340 KB Output is correct
4 Correct 29 ms 404 KB Output is correct
5 Correct 11 ms 1108 KB Output is correct
6 Correct 26 ms 732 KB Output is correct
7 Correct 27 ms 660 KB Output is correct
8 Correct 14 ms 724 KB Output is correct
9 Correct 13 ms 732 KB Output is correct
10 Correct 7 ms 1108 KB Output is correct
11 Correct 17 ms 728 KB Output is correct
12 Correct 20 ms 736 KB Output is correct
13 Correct 7 ms 1108 KB Output is correct
14 Correct 13 ms 724 KB Output is correct
15 Correct 26 ms 416 KB Output is correct
16 Correct 27 ms 340 KB Output is correct
17 Correct 22 ms 724 KB Output is correct
18 Correct 9 ms 1040 KB Output is correct
19 Correct 17 ms 724 KB Output is correct
20 Correct 21 ms 724 KB Output is correct
21 Correct 1437 ms 11056 KB Output is correct
22 Correct 1463 ms 11752 KB Output is correct
23 Correct 1406 ms 11316 KB Output is correct
24 Correct 931 ms 13500 KB Output is correct
25 Correct 1331 ms 22228 KB Output is correct
26 Correct 1360 ms 23320 KB Output is correct
27 Correct 1568 ms 11152 KB Output is correct
28 Correct 1501 ms 11024 KB Output is correct
29 Correct 1412 ms 11328 KB Output is correct
30 Correct 1261 ms 4584 KB Output is correct
31 Correct 1095 ms 5976 KB Output is correct
32 Correct 938 ms 19664 KB Output is correct
33 Correct 833 ms 13032 KB Output is correct
34 Correct 873 ms 13372 KB Output is correct
35 Correct 830 ms 13724 KB Output is correct
36 Correct 870 ms 13528 KB Output is correct
37 Correct 1039 ms 17632 KB Output is correct
38 Correct 689 ms 14912 KB Output is correct
39 Correct 1056 ms 15424 KB Output is correct
40 Correct 1269 ms 22076 KB Output is correct
41 Correct 1231 ms 24916 KB Output is correct
42 Correct 1050 ms 19708 KB Output is correct
43 Correct 862 ms 13916 KB Output is correct
44 Correct 1075 ms 19436 KB Output is correct
45 Correct 981 ms 18676 KB Output is correct
46 Correct 769 ms 15232 KB Output is correct
47 Correct 762 ms 15376 KB Output is correct
48 Correct 790 ms 14972 KB Output is correct
49 Correct 421 ms 11940 KB Output is correct
50 Correct 1145 ms 11136 KB Output is correct
51 Correct 1185 ms 11124 KB Output is correct
52 Correct 458 ms 11304 KB Output is correct
53 Correct 912 ms 13632 KB Output is correct
54 Correct 836 ms 17216 KB Output is correct
55 Correct 905 ms 17864 KB Output is correct
56 Correct 904 ms 17504 KB Output is correct
57 Correct 848 ms 13412 KB Output is correct
58 Correct 818 ms 13032 KB Output is correct
59 Correct 871 ms 13032 KB Output is correct
60 Correct 848 ms 13048 KB Output is correct
61 Correct 933 ms 19868 KB Output is correct
62 Correct 933 ms 20192 KB Output is correct
63 Correct 1316 ms 24316 KB Output is correct
64 Correct 1056 ms 20100 KB Output is correct
65 Correct 904 ms 18804 KB Output is correct
66 Correct 728 ms 14828 KB Output is correct
67 Correct 849 ms 16712 KB Output is correct
68 Correct 913 ms 19256 KB Output is correct
69 Correct 1047 ms 13276 KB Output is correct
70 Correct 1031 ms 13308 KB Output is correct
71 Correct 1000 ms 13132 KB Output is correct
72 Correct 1033 ms 13520 KB Output is correct
73 Correct 1100 ms 19472 KB Output is correct
74 Correct 1534 ms 3060 KB Output is correct
75 Correct 1181 ms 20360 KB Output is correct
76 Correct 802 ms 4848 KB Output is correct
77 Correct 1062 ms 17124 KB Output is correct
78 Correct 1201 ms 19780 KB Output is correct
79 Correct 1072 ms 14504 KB Output is correct
80 Correct 1272 ms 21540 KB Output is correct
81 Correct 981 ms 18256 KB Output is correct
82 Correct 979 ms 15752 KB Output is correct
83 Correct 1277 ms 19196 KB Output is correct
84 Correct 989 ms 19080 KB Output is correct
85 Correct 1457 ms 12380 KB Output is correct
86 Correct 1317 ms 11936 KB Output is correct
87 Correct 1363 ms 11748 KB Output is correct
88 Correct 1461 ms 11580 KB Output is correct
89 Correct 1030 ms 13032 KB Output is correct
90 Correct 1033 ms 13092 KB Output is correct
91 Correct 1070 ms 13300 KB Output is correct
92 Correct 1028 ms 13372 KB Output is correct
93 Correct 1475 ms 7044 KB Output is correct
94 Correct 1126 ms 2380 KB Output is correct
95 Correct 1066 ms 15052 KB Output is correct
96 Correct 1493 ms 2000 KB Output is correct
97 Correct 1055 ms 19184 KB Output is correct
98 Correct 1327 ms 22536 KB Output is correct
99 Correct 1298 ms 21304 KB Output is correct
100 Correct 1280 ms 22396 KB Output is correct
101 Correct 934 ms 14512 KB Output is correct
102 Correct 917 ms 14588 KB Output is correct
103 Correct 1038 ms 18456 KB Output is correct
104 Correct 942 ms 16788 KB Output is correct
105 Correct 1355 ms 11184 KB Output is correct
106 Correct 1371 ms 11132 KB Output is correct
107 Correct 1377 ms 11424 KB Output is correct
108 Correct 1279 ms 11124 KB Output is correct
109 Correct 991 ms 15020 KB Output is correct
110 Correct 1083 ms 16888 KB Output is correct
111 Correct 1450 ms 24656 KB Output is correct
112 Correct 1339 ms 22768 KB Output is correct
113 Correct 1146 ms 13416 KB Output is correct
114 Correct 1010 ms 13472 KB Output is correct
115 Correct 1110 ms 13008 KB Output is correct
116 Correct 1000 ms 12932 KB Output is correct
117 Correct 933 ms 17928 KB Output is correct
118 Correct 913 ms 15420 KB Output is correct
119 Correct 983 ms 14376 KB Output is correct
120 Correct 1049 ms 17748 KB Output is correct
121 Correct 1081 ms 18356 KB Output is correct
122 Correct 1201 ms 19540 KB Output is correct
123 Correct 896 ms 16276 KB Output is correct
124 Correct 895 ms 14000 KB Output is correct
125 Correct 2824 ms 32508 KB Output is correct
126 Correct 2706 ms 32368 KB Output is correct
127 Correct 2920 ms 32556 KB Output is correct
128 Correct 2821 ms 32324 KB Output is correct
129 Correct 2842 ms 32920 KB Output is correct
130 Correct 2865 ms 31616 KB Output is correct
131 Correct 3709 ms 4800 KB Output is correct
132 Correct 3241 ms 21012 KB Output is correct
133 Correct 3022 ms 35036 KB Output is correct
134 Correct 1539 ms 7848 KB Output is correct
135 Correct 4594 ms 40364 KB Output is correct
136 Correct 2781 ms 7844 KB Output is correct
137 Execution timed out 5071 ms 50140 KB Time limit exceeded
138 Halted 0 ms 0 KB -