oj.uz

Submission #758585

# Submission time Handle Problem Language Result Execution time Memory
758585 2023-06-14T23:39:57 Z scanhex Segments (IZhO18_segments) C++17
22 / 100
 1474 ms 22936 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;
	vector<pair<int,int>> erblock;
	static2d st;

	void check_rebuild() {
		if (block.size() + erblock.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);
			sort(erblock.begin(), erblock.end(), ycmp);
			all.clear();
			int ptr = 0; 
			for (auto x : erblock) {
				 while (ptr < newall.size() && ycmp(newall[ptr], x))
					 all.push_back(newall[ptr++]);
				 // always true? 
				 if (ptr < newall.size() && newall[ptr] == x)
					 ++ptr;
			}
			while (ptr < newall.size())
				all.push_back(newall[ptr++]);
			block.clear();
			erblock.clear();
			st.build(all);
		}
	}
	
	void insert(int x, int y) {
		block.push_back({x, y});
		check_rebuild();
	}

	void erase(int x, int y) {
		erblock.push_back({x, y});
		check_rebuild();
	}

	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;
		for (auto p : erblock) 
			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);
	}
	void erase(int l, int r) {
		--tot;
		rofl_l.erase(l, r - l);
		rofl_r.erase(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;
	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;
			add.erase(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);
			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;
      |       ^~~
segments.cpp: In member function 'void rofl2d::check_rebuild()':
segments.cpp:115:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |      while (ptr < newall.size() && ycmp(newall[ptr], x))
      |             ~~~~^~~~~~~~~~~~~~~
segments.cpp:118:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |      if (ptr < newall.size() && newall[ptr] == x)
      |          ~~~~^~~~~~~~~~~~~~~
segments.cpp:121:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |    while (ptr < newall.size())
      |           ~~~~^~~~~~~~~~~~~~~

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 14 ms 340 KB Output is correct
4 Correct 12 ms 340 KB Output is correct
5 Correct 8 ms 1144 KB Output is correct
6 Correct 19 ms 760 KB Output is correct
7 Correct 13 ms 468 KB Output is correct
8 Correct 11 ms 876 KB Output is correct
9 Correct 11 ms 956 KB Output is correct
10 Correct 7 ms 1148 KB Output is correct
11 Correct 15 ms 756 KB Output is correct
12 Correct 15 ms 852 KB Output is correct
13 Correct 6 ms 1064 KB Output is correct
14 Correct 11 ms 868 KB Output is correct
15 Correct 12 ms 384 KB Output is correct
16 Correct 12 ms 380 KB Output is correct
17 Correct 18 ms 608 KB Output is correct
18 Correct 8 ms 1108 KB Output is correct
19 Correct 14 ms 668 KB Output is correct
20 Correct 12 ms 696 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1137 ms 11068 KB Output is correct
2 Correct 1212 ms 11320 KB Output is correct
3 Correct 1211 ms 11416 KB Output is correct
4 Correct 946 ms 12652 KB Output is correct
5 Correct 1291 ms 21740 KB Output is correct
6 Correct 1421 ms 22936 KB Output is correct
7 Correct 1380 ms 11084 KB Output is correct
8 Correct 1255 ms 10692 KB Output is correct
9 Correct 1271 ms 10868 KB Output is correct
10 Correct 1118 ms 4728 KB Output is correct
11 Correct 934 ms 6036 KB Output is correct
12 Correct 825 ms 17972 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 1072 KB Output is correct
2 Correct 271 ms 1220 KB Output is correct
3 Correct 304 ms 1100 KB Output is correct
4 Correct 274 ms 1132 KB Output is correct
5 Correct 1018 ms 18116 KB Output is correct
6 Correct 659 ms 13436 KB Output is correct
7 Correct 979 ms 14692 KB Output is correct
8 Correct 1250 ms 22692 KB Output is correct
9 Correct 1285 ms 21488 KB Output is correct
10 Correct 1016 ms 16684 KB Output is correct
11 Correct 323 ms 1928 KB Output is correct
12 Incorrect 1077 ms 17976 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 1096 KB Output is correct
2 Correct 267 ms 1096 KB Output is correct
3 Correct 288 ms 1068 KB Output is correct
4 Correct 317 ms 1112 KB Output is correct
5 Correct 1139 ms 18880 KB Output is correct
6 Correct 1474 ms 3216 KB Output is correct
7 Correct 1176 ms 19784 KB Output is correct
8 Correct 703 ms 4860 KB Output is correct
9 Incorrect 872 ms 8696 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
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 14 ms 340 KB Output is correct
4 Correct 12 ms 340 KB Output is correct
5 Correct 8 ms 1144 KB Output is correct
6 Correct 19 ms 760 KB Output is correct
7 Correct 13 ms 468 KB Output is correct
8 Correct 11 ms 876 KB Output is correct
9 Correct 11 ms 956 KB Output is correct
10 Correct 7 ms 1148 KB Output is correct
11 Correct 15 ms 756 KB Output is correct
12 Correct 15 ms 852 KB Output is correct
13 Correct 6 ms 1064 KB Output is correct
14 Correct 11 ms 868 KB Output is correct
15 Correct 12 ms 384 KB Output is correct
16 Correct 12 ms 380 KB Output is correct
17 Correct 18 ms 608 KB Output is correct
18 Correct 8 ms 1108 KB Output is correct
19 Correct 14 ms 668 KB Output is correct
20 Correct 12 ms 696 KB Output is correct
21 Correct 1137 ms 11068 KB Output is correct
22 Correct 1212 ms 11320 KB Output is correct
23 Correct 1211 ms 11416 KB Output is correct
24 Correct 946 ms 12652 KB Output is correct
25 Correct 1291 ms 21740 KB Output is correct
26 Correct 1421 ms 22936 KB Output is correct
27 Correct 1380 ms 11084 KB Output is correct
28 Correct 1255 ms 10692 KB Output is correct
29 Correct 1271 ms 10868 KB Output is correct
30 Correct 1118 ms 4728 KB Output is correct
31 Correct 934 ms 6036 KB Output is correct
32 Correct 825 ms 17972 KB Output is correct
33 Correct 265 ms 1096 KB Output is correct
34 Correct 267 ms 1096 KB Output is correct
35 Correct 288 ms 1068 KB Output is correct
36 Correct 317 ms 1112 KB Output is correct
37 Correct 1139 ms 18880 KB Output is correct
38 Correct 1474 ms 3216 KB Output is correct
39 Correct 1176 ms 19784 KB Output is correct
40 Correct 703 ms 4860 KB Output is correct
41 Incorrect 872 ms 8696 KB Output isn't correct
42 Halted 0 ms 0 KB -

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 14 ms 340 KB Output is correct
4 Correct 12 ms 340 KB Output is correct
5 Correct 8 ms 1144 KB Output is correct
6 Correct 19 ms 760 KB Output is correct
7 Correct 13 ms 468 KB Output is correct
8 Correct 11 ms 876 KB Output is correct
9 Correct 11 ms 956 KB Output is correct
10 Correct 7 ms 1148 KB Output is correct
11 Correct 15 ms 756 KB Output is correct
12 Correct 15 ms 852 KB Output is correct
13 Correct 6 ms 1064 KB Output is correct
14 Correct 11 ms 868 KB Output is correct
15 Correct 12 ms 384 KB Output is correct
16 Correct 12 ms 380 KB Output is correct
17 Correct 18 ms 608 KB Output is correct
18 Correct 8 ms 1108 KB Output is correct
19 Correct 14 ms 668 KB Output is correct
20 Correct 12 ms 696 KB Output is correct
21 Correct 1137 ms 11068 KB Output is correct
22 Correct 1212 ms 11320 KB Output is correct
23 Correct 1211 ms 11416 KB Output is correct
24 Correct 946 ms 12652 KB Output is correct
25 Correct 1291 ms 21740 KB Output is correct
26 Correct 1421 ms 22936 KB Output is correct
27 Correct 1380 ms 11084 KB Output is correct
28 Correct 1255 ms 10692 KB Output is correct
29 Correct 1271 ms 10868 KB Output is correct
30 Correct 1118 ms 4728 KB Output is correct
31 Correct 934 ms 6036 KB Output is correct
32 Correct 825 ms 17972 KB Output is correct
33 Correct 286 ms 1072 KB Output is correct
34 Correct 271 ms 1220 KB Output is correct
35 Correct 304 ms 1100 KB Output is correct
36 Correct 274 ms 1132 KB Output is correct
37 Correct 1018 ms 18116 KB Output is correct
38 Correct 659 ms 13436 KB Output is correct
39 Correct 979 ms 14692 KB Output is correct
40 Correct 1250 ms 22692 KB Output is correct
41 Correct 1285 ms 21488 KB Output is correct
42 Correct 1016 ms 16684 KB Output is correct
43 Correct 323 ms 1928 KB Output is correct
44 Incorrect 1077 ms 17976 KB Output isn't correct
45 Halted 0 ms 0 KB -