oj.uz

Submission #758557

# Submission time Handle Problem Language Result Execution time Memory
758557 2023-06-14T22:00:14 Z scanhex Segments (IZhO18_segments) C++17
7 / 100
 5000 ms 3704 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 rofl2d {
	vector<pair<int,int>> pts;
	void insert(int x, int y) {
		pts.push_back({x, y});
	}

	// all inclusive
	int get(int x1, int x2, int y1, int y2) {
		int res = 0;
		for (auto p : pts) 
			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 (k == 0) return tot;
		int res = tot;
		res -= rofl_l.get(r - k + 2, oo, k - 1, oo);
		res -= rofl_r.get(0, l + k - 2, k - 1, oo);
		res -= rofl_l.get(0, oo, 0, k - 2);
		return res;
	}
};


int main() {
	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';
		}
	}
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 24 ms 520 KB Output is correct
4 Correct 25 ms 492 KB Output is correct
5 Correct 31 ms 596 KB Output is correct
6 Correct 40 ms 468 KB Output is correct
7 Correct 29 ms 468 KB Output is correct
8 Correct 26 ms 540 KB Output is correct
9 Correct 21 ms 552 KB Output is correct
10 Correct 8 ms 596 KB Output is correct
11 Correct 53 ms 576 KB Output is correct
12 Correct 54 ms 572 KB Output is correct
13 Correct 11 ms 588 KB Output is correct
14 Correct 28 ms 468 KB Output is correct
15 Correct 24 ms 524 KB Output is correct
16 Correct 24 ms 488 KB Output is correct
17 Correct 29 ms 548 KB Output is correct
18 Correct 14 ms 636 KB Output is correct
19 Correct 24 ms 468 KB Output is correct
20 Correct 24 ms 468 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5025 ms 3704 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5032 ms 3444 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5039 ms 3300 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 24 ms 520 KB Output is correct
4 Correct 25 ms 492 KB Output is correct
5 Correct 31 ms 596 KB Output is correct
6 Correct 40 ms 468 KB Output is correct
7 Correct 29 ms 468 KB Output is correct
8 Correct 26 ms 540 KB Output is correct
9 Correct 21 ms 552 KB Output is correct
10 Correct 8 ms 596 KB Output is correct
11 Correct 53 ms 576 KB Output is correct
12 Correct 54 ms 572 KB Output is correct
13 Correct 11 ms 588 KB Output is correct
14 Correct 28 ms 468 KB Output is correct
15 Correct 24 ms 524 KB Output is correct
16 Correct 24 ms 488 KB Output is correct
17 Correct 29 ms 548 KB Output is correct
18 Correct 14 ms 636 KB Output is correct
19 Correct 24 ms 468 KB Output is correct
20 Correct 24 ms 468 KB Output is correct
21 Execution timed out 5025 ms 3704 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 24 ms 520 KB Output is correct
4 Correct 25 ms 492 KB Output is correct
5 Correct 31 ms 596 KB Output is correct
6 Correct 40 ms 468 KB Output is correct
7 Correct 29 ms 468 KB Output is correct
8 Correct 26 ms 540 KB Output is correct
9 Correct 21 ms 552 KB Output is correct
10 Correct 8 ms 596 KB Output is correct
11 Correct 53 ms 576 KB Output is correct
12 Correct 54 ms 572 KB Output is correct
13 Correct 11 ms 588 KB Output is correct
14 Correct 28 ms 468 KB Output is correct
15 Correct 24 ms 524 KB Output is correct
16 Correct 24 ms 488 KB Output is correct
17 Correct 29 ms 548 KB Output is correct
18 Correct 14 ms 636 KB Output is correct
19 Correct 24 ms 468 KB Output is correct
20 Correct 24 ms 468 KB Output is correct
21 Execution timed out 5025 ms 3704 KB Time limit exceeded
22 Halted 0 ms 0 KB -