oj.uz

Submission #758574

# Submission time Handle Problem Language Result Execution time Memory
758574 2023-06-14T22:59:54 Z scanhex Segments (IZhO18_segments) C++17
16 / 100
 5000 ms 24180 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() {
		sort(coords.begin(), coords.end());
	}

	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 << l << ' ' << r << ' ' << itr - itl << '\n';
		return itr - itl;
	}
};

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 < xs.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 = 1000;

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) {
			 for (auto& x : block)
				 all.push_back(x);
			 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() {
	ds smart;
	dss stupid;
	for (int i = 0; i < 1000; ++i) {
		int x = rand() % 5, y = rand() % 5;
		if (x > y) swap(x, y);
		cerr << "1 " << x << ' ' << y << '\n';
		smart.insert(x, y);
		stupid.insert(x, y);

		int a = rand() % 5, b = rand() % 5, k = rand() % 5;
		if (a > b) swap(a, b);
		if (smart.get(a, b, k) != stupid.get(a, b, k)) {
			cerr << smart.get(a, b, k) << ' ' << stupid.get(a, b, k) << '\n';
			cerr << "3 " << a << ' ' << b << ' ' << k << '\n';
			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:53:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<static1d>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   for (++x; x < v.size(); x = (x | x - 1) + 1)
      |             ~~^~~~~~~~~~
segments.cpp:53:38: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
   53 |   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:69:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |   for (int i = 0; i < xs.size(); ++i)
      |                   ~~^~~~~~~~~~~
segments.cpp: In member function 'int static2d::get(int, int, int)':
segments.cpp:75:7: warning: unused variable 'xrr' [-Wunused-variable]
   75 |   int xrr = xr;
      |       ^~~

Subtask #1
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 16 ms 596 KB Output is correct
4 Correct 16 ms 740 KB Output is correct
5 Correct 12 ms 1108 KB Output is correct
6 Incorrect 16 ms 968 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1747 ms 11888 KB Output is correct
2 Correct 1792 ms 14056 KB Output is correct
3 Correct 1808 ms 13792 KB Output is correct
4 Correct 1966 ms 14544 KB Output is correct
5 Execution timed out 5051 ms 23420 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1339 ms 14592 KB Output is correct
2 Correct 1367 ms 16568 KB Output is correct
3 Correct 1331 ms 17044 KB Output is correct
4 Correct 1310 ms 16412 KB Output is correct
5 Correct 2800 ms 19128 KB Output is correct
6 Correct 1973 ms 15808 KB Output is correct
7 Correct 2256 ms 17500 KB Output is correct
8 Correct 4818 ms 23820 KB Output is correct
9 Correct 4706 ms 24180 KB Output is correct
10 Correct 3214 ms 20648 KB Output is correct
11 Correct 1320 ms 15536 KB Output is correct
12 Correct 3330 ms 21972 KB Output is correct
13 Correct 2782 ms 19932 KB Output is correct
14 Correct 1811 ms 17184 KB Output is correct
15 Correct 1672 ms 16904 KB Output is correct
16 Correct 1486 ms 16204 KB Output is correct
17 Correct 1319 ms 13704 KB Output is correct
18 Correct 1599 ms 13112 KB Output is correct
19 Correct 1594 ms 13384 KB Output is correct
20 Correct 1288 ms 13584 KB Output is correct
21 Correct 1357 ms 15236 KB Output is correct
22 Correct 2045 ms 18752 KB Output is correct
23 Correct 2396 ms 20524 KB Output is correct
24 Correct 2119 ms 18456 KB Output is correct
25 Correct 1369 ms 16460 KB Output is correct
26 Correct 1264 ms 16536 KB Output is correct
27 Correct 1341 ms 16296 KB Output is correct
28 Correct 1373 ms 16536 KB Output is correct
29 Correct 2583 ms 21148 KB Output is correct
30 Correct 2577 ms 21176 KB Output is correct
31 Correct 4758 ms 23052 KB Output is correct
32 Correct 3100 ms 20988 KB Output is correct
33 Correct 2864 ms 21052 KB Output is correct
34 Correct 1554 ms 16648 KB Output is correct
35 Correct 2214 ms 18800 KB Output is correct
36 Correct 3110 ms 21112 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1427 ms 15312 KB Output is correct
2 Correct 1382 ms 16664 KB Output is correct
3 Correct 1422 ms 16732 KB Output is correct
4 Correct 1395 ms 17232 KB Output is correct
5 Correct 3246 ms 20448 KB Output is correct
6 Incorrect 798 ms 6308 KB Output isn't correct
7 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 16 ms 596 KB Output is correct
4 Correct 16 ms 740 KB Output is correct
5 Correct 12 ms 1108 KB Output is correct
6 Incorrect 16 ms 968 KB Output isn't correct
7 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 16 ms 596 KB Output is correct
4 Correct 16 ms 740 KB Output is correct
5 Correct 12 ms 1108 KB Output is correct
6 Incorrect 16 ms 968 KB Output isn't correct
7 Halted 0 ms 0 KB -