QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#186158 | #5463. Range Closest Pair of Points Query | APJifengc | WA | 144ms | 52868kb | C++14 | 2.9kb | 2023-09-23 09:52:46 | 2023-09-23 09:52:46 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 250005, B = 500;
int n, q;
int x[MAXN], y[MAXN];
vector<pair<int, int>> qs[MAXN];
long long dis(int i, int j) { return 1ll * (x[i] - x[j]) * (x[i] - x[j]) + 1ll * (y[i] - y[j]) * (y[i] - y[j]); }
long long ans[MAXN];
unordered_map<long long, pair<int, int>> mp;
int L[MAXN], R[MAXN], bl[MAXN];
long long val[MAXN], valb[MAXN];
void add(int d, long long v) { val[d] = min(val[d], v), valb[bl[d]] = min(valb[bl[d]], v); }
long long query(int l, int r) {
long long ans = LLONG_MAX;
for (int i = l; i <= R[bl[l]]; i++) ans = min(ans, val[i]);
r = bl[r];
for (int i = bl[l] + 1; i <= r; i++) ans = min(ans, valb[i]);
return ans;
}
vector<int> pts[MAXN];
int p[MAXN];
int bx[MAXN], by[MAXN];
long long id(int x, int y) { return ((x + 5ll) << 30) | (y + 5ll); }
int main() {
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++) scanf("%d%d", &x[i], &y[i]);
for (int i = 1; i <= q; i++) {
int l, r; scanf("%d%d", &l, &r);
qs[r].push_back({ l, i });
}
for (int l = 1, r, i = 1; l <= n; l = r + 1, i++) {
r = min(n, l + B - 1);
L[i] = l, R[i] = r;
for (int j = l; j <= r; j++) bl[j] = i;
}
auto ins = [&](int i, int s, int r) {
for (int j = s + 1; j <= s + 3 && j < r; j++) {
// printf("(%d, %d)\n", p[i], p[j]);
pts[p[j]].push_back(p[i]);
}
};
memset(val, 0x3f, sizeof val);
memset(valb, 0x3f, sizeof valb);
for (int k = 0; k <= 29; k++) {
for (int i = 1; i <= n; i++) p[i] = i, bx[i] = x[i] >> k, by[i] = y[i] >> k;
sort(p + 1, p + 1 + n, [&](int i, int j) {
return bx[i] == bx[j] ? (by[i] == by[j] ? i < j : by[i] < by[j]) : bx[i] < bx[j];
});
for (int l = 1, r = 1; l <= n; l = r) {
while (r <= n && bx[p[l]] == bx[p[r]] && by[p[l]] == by[p[r]]) r++;
int X = bx[p[l]], Y = by[p[l]];
mp[id(X, Y)] = { l, r };
for (int i = l; i < r; i++) ins(i, i, r);
}
for (int l = 1, r = 1; l <= n; l = r) {
while (r <= n && bx[p[l]] == bx[p[r]] && by[p[l]] == by[p[r]]) r++;
int X = bx[p[l]], Y = by[p[l]];
for (auto [dx, dy] : vector<pair<int, int>>{ {-1, 1}, {0, 1}, {1, 1}, {1, 0} }) {
if (!mp.count(id(X + dx, Y + dy))) continue;
auto [pl, pr] = mp[id(X + dx, Y + dy)];
int px = l, py = pl;
while (px != r && py != pr) {
if (p[px] < p[py]) ins(px, py, pr), px++;
else ins(py, px, r), py++;
}
}
}
mp.clear();
}
for (int i = 1; i <= n; i++) {
for (auto p : pts[i]) add(p, dis(p, i));
for (auto p : qs[i]) ans[p.second] = query(p.first, i);
}
for (int i = 1; i <= q; i++) printf("%lld\n", ans[i]);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 26412kb
input:
5 5 2 4 1 1 3 3 5 1 4 2 1 5 2 3 2 4 3 5 1 3
output:
2 8 8 2 2
result:
ok 5 number(s): "2 8 8 2 2"
Test #2:
score: 0
Accepted
time: 0ms
memory: 26396kb
input:
2 1 1 1 1 1 1 2
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 0ms
memory: 26272kb
input:
2 1 1 100000000 100000000 1 1 2
output:
19999999600000002
result:
ok 1 number(s): "19999999600000002"
Test #4:
score: -100
Wrong Answer
time: 144ms
memory: 52868kb
input:
20000 250000 3 10 5 4 4 7 1 5 2 1 10 6 2 3 8 4 2 1 8 5 9 8 7 7 4 5 2 7 9 4 9 10 3 2 9 5 10 2 9 2 3 1 9 9 6 5 9 5 9 10 9 1 1 2 8 8 3 4 7 6 6 2 6 8 6 6 8 4 10 2 1 1 10 2 8 3 4 4 5 5 5 1 4 9 7 6 6 8 6 4 1 6 10 3 3 2 4 10 6 8 9 7 2 10 7 8 10 7 3 2 5 1 6 4 7 9 1 3 4 9 4 8 9 4 5 2 2 2 9 2 9 2 9 6 6 9 8 7 ...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer 94496th numbers differ - expected: '2', found: '5'