QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#95002#6136. Airdropysghwzp#TL 2ms3372kbC++202.1kb2023-04-08 16:59:392023-04-08 16:59:41

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-08 16:59:41]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:3372kb
  • [2023-04-08 16:59:39]
  • 提交

answer

#include <bits/stdc++.h>

using i64 = long long;

void solve() {
	int n, y0;
	std::cin >> n >> y0;

	std::vector<int> x(n), y(n);
	std::vector<int> v;
	for (int i = 0; i < n; i++) {
		std::cin >> x[i] >> y[i];
		v.push_back(x[i] - 1);
		v.push_back(x[i]);
		v.push_back(x[i] + 1);
	}
	std::sort(v.begin(), v.end());
	v.erase(std::unique(v.begin(), v.end()), v.end());

	int m = v.size();
	std::vector<int> ans(m);
	auto get = [&](int x) {
		return std::lower_bound(v.begin(), v.end(), x) - v.begin();
	};
	for (int i = 0; i < n; i++) {
		int t = get(x[i]);
		ans[t] += 1;
		ans[t + 1] -= 1;
	}

	std::map<int, std::vector<int>> f;
	for (int i = 0; i < n; i++) {
		f[-x[i] + std::abs(y[i] - y0)].push_back(i);
	}
	for (auto [_, p] : f) {
		std::sort(p.begin(), p.end(), [&](int i, int j) {
			return x[i] < x[j];
		});

		for (int i = 0; i < p.size(); ) {
			if (i + 1 == p.size()) {
				int t = get(x[p[i]] + 1);
				ans[t] += 1;
				break;
			} else {
				int t = get(x[p[i]] + 1);
				ans[t] += 1;
				t = get(x[p[i + 1]] + 1);
				ans[t] -= 1;
				i += 2;
				if (i < p.size() && x[p[i]] == x[p[i - 1]]) {
					i += 1;
				}
			}
		}
	}

	f.clear();
	for (int i = 0; i < n; i++) {
		f[x[i] + std::abs(y[i] - y0)].push_back(i);
	}
	for (auto [_, p] : f) {
		std::sort(p.begin(), p.end(), [&](int i, int j) {
			return x[i] > x[j];
		});

		for (int i = 0; i < p.size(); ) {
			if (i + 1 == p.size()) {
				int t = get(x[p[i]]);
				ans[0] += 1;
				ans[t] -= 1;
				break;
			} else {
				int t = get(x[p[i]]);
				ans[t] -= 1;
				t = get(x[p[i + 1]]);
				ans[t] += 1;
				i += 2;
				if (i < p.size() && x[p[i]] == x[p[i - 1]]) {
					i += 1;
				}
			}
		}
	}

	for (int i = 1; i < m; i++) {
		ans[i] += ans[i - 1];
	}
	int pmin = *std::min_element(ans.begin(), ans.end());
	int pmax = *std::max_element(ans.begin(), ans.end());
	std::cout << pmin << " " << pmax << "\n";
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int T;
	std::cin >> T;

	while (T--) {
		solve();
	}

	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 3372kb

input:

3
3 2
1 2
2 1
3 5
3 3
2 1
2 5
4 3
2 3
1 3
4 3

output:

1 3
0 3
2 2

result:

ok 6 numbers

Test #2:

score: -100
Time Limit Exceeded

input:

3508
6 1
7 1
1 1
9 1
10 1
3 1
4 1
3 8
8 9
8 7
1 8
9 5
10 1
10 8
10 2
5 1
9 9
5 9
10 9
6 4
4 7
6 7
10 5
3 8
9 5
9 9
7 5
4 7
10 5
6 9
9 5
6 6
9 3
3 2
5 1
3 8
6 4
5 9
10 2
2 9
10 10
10 8
4 1
7 1
6 1
3 1
5 1
2 4
9 3
3 3
4 5
3 8
9 6
9 9
6 3
9 5
9 3
2 9
9 1
9 2
4 1
5 4
5 6
6 5
9 8
4 1
2 1
5 1
7 1
3 1
9 10...

output:

6 6
1 3
1 5
2 6
2 6
0 2
4 4
2 2
4 4
4 7
4 4
9 9
4 6
0 3
2 6
2 2
2 6
10 10
9 9
1 3
2 4
0 2
2 4
4 7
6 6
9 9
2 2
2 2
3 5
1 4
2 2
1 1
3 5
4 7
3 6
1 1
5 7
5 5
1 3
2 2
1 7
1 1
4 6
2 4
2 6
2 4
1 7
2 4
9 9
0 3
1 1
3 8
2 2
2 2
9 9
3 7
4 4
4 6
2 5
0 2
2 5
3 3
0 4
4 4
2 4
2 2
4 6
6 6
6 6
0 2
2 6
2 4
2 6
2 5
1 ...

result: