QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#95002 | #6136. Airdrop | ysghwzp# | TL | 2ms | 3372kb | C++20 | 2.1kb | 2023-04-08 16:59:39 | 2023-04-08 16:59:41 |
Judging History
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 ...