QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#122622 | #5463. Range Closest Pair of Points Query | Ender32k | WA | 3ms | 23992kb | C++20 | 4.1kb | 2023-07-10 20:39:37 | 2023-07-10 20:39:51 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
using namespace std;
namespace vbzIO {
char ibuf[(1 << 20) + 1], *iS, *iT;
#if ONLINE_JUDGE
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
#else
#define gh() getchar()
#endif
#define mt make_tuple
#define mp make_pair
#define fi first
#define se second
#define pc putchar
#define pb emplace_back
#define ins insert
#define era erase
typedef tuple<int, int, int> tu3;
typedef pair<int, int> pi;
inline int rd() {
char ch = gh();
int x = 0;
bool t = 0;
while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
return t ? ~(x - 1) : x;
}
inline void wr(ll x) {
if (x < 0) {
x = ~(x - 1);
putchar('-');
}
if (x > 9)
wr(x / 10);
putchar(x % 10 + '0');
}
}
using namespace vbzIO;
int max(int i, int j) { return i > j ? i : j; }
ll min(ll i, ll j) { return i > j ? j : i; }
mt19937 rnd(time(0));
const int N = 2.5e5 + 250;
const int B = 510;
const int P = 998244353;
const ll inf = 2e18;
const int W = 1000;
int f[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int n, m, b, x[N], y[N], id[N];
vector<pi> qr[N];
vector<int> g[N];
ll ans[N];
map<pi, pi> t;
ll dis(int i, int j) {
return 1ll * (x[i] - x[j]) * (x[i] - x[j]) + 1ll * (y[i] - y[j]) * (y[i] - y[j]);
}
int pos[N], lp[N], rp[N];
ll mn[B], a[N];
void mdf(int p, ll q) {
a[p] = min(a[p], q);
mn[pos[p]] = min(mn[pos[p]], q);
}
ll qry(int p, int q) {
if (pos[p] == pos[q]) {
ll res = inf;
for (int i = p; i <= q; i++)
res = min(res, a[i]);
return res;
}
ll res = inf;
for (int i = pos[p] + 1; i <= pos[q] - 1; i++)
res = min(res, mn[i]);
for (int i = p; i <= rp[pos[p]]; i++)
res = min(res, a[i]);
for (int i = lp[pos[q]]; i <= q; i++)
res = min(res, a[i]);
return res;
}
int X(int i, int k) { return x[i] >> k; }
int Y(int i, int k) { return y[i] >> k; }
int main() {
n = rd(), m = rd(), b = sqrt(n);
for (int i = 1; i <= b; i++)
lp[i] = (i - 1) * b + 1, rp[i] = i * b;
if (rp[b] < n) b++, lp[b] = rp[b - 1] + 1, rp[b] = n;
for (int i = 1; i <= b; i++) {
mn[i] = inf;
for (int j = lp[i]; j <= rp[i]; j++)
pos[j] = i;
}
for (int i = 1; i <= n; i++) x[i] = rd(), y[i] = rd(), id[i] = i, a[i] = inf;
for (int i = 1, l, r; i <= m; i++) l = rd(), r = rd(), qr[r].pb(mp(l, i));
for (int k = 0; k <= 27; k++) {
for (int i = 1; i <= n; i++) id[i] = i;
sort(id + 1, id + n + 1, [&] (int &i, int &j) { return X(i, k) == X(j, k) ? Y(i, k) < Y(j, k) : X(i, k) < X(j, k); });
for (int l = 1; l <= n; l++) {
int r = l;
while (r < n && X(id[r + 1], k) == X(id[l], k) && Y(id[r + 1], k) == Y(id[l], k)) r++;
// cout << l << " " << r << endl;
sort(id + l, id + r + 1), t[mp(X(id[l], k), Y(id[l], k))] = mp(l, r);
for (int i = l; i <= r; i++)
for (int j = i + 1; j <= min(r, i + 3); j++)
g[id[j]].pb(id[i]);
l = r;
}
for (int l = 1; l <= n; l++) {
int r = t[mp(X(l, k), Y(l, k))].se, sx = X(l, k), sy = Y(l, k);
for (int i = 0; i <= 3; i++) {
if (!t.count(mp(sx + f[i][0], sy + f[i][1]))) continue;
int tx = sx + f[i][0], ty = sy + f[i][1];
auto [tl, tr] = t[mp(tx, ty)];
// cout << l << " " << r << " " << tl << " " << tr << endl;
vector<int> tp;
tp.ins(tp.end(), id + l, id + r + 1);
tp.ins(tp.end(), id + tl, id + tr + 1);
inplace_merge(tp.begin(), tp.begin() + r - l + 1, tp.end());
for (int p = 0; p < tp.size(); p++)
for (int q = p + 1; q <= min(p + 3, tp.size() - 1); q++)
g[tp[q]].pb(tp[p]);
}
l = r;
}
t.clear();
}
for (int i = 1; i <= n; i++) {
for (int j : g[i]) mdf(j, dis(i, j))/*, cout << i << " " << j << endl*/;
for (auto [j, k] : qr[i]) ans[k] = qry(j, i);
}
for (int i = 1; i <= m; i++)
wr(ans[i]), puts("");
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 23992kb
input:
5 5 2 4 1 1 3 3 5 1 4 2 1 5 2 3 2 4 3 5 1 3
output:
0 0 0 0 0
result:
wrong answer 1st numbers differ - expected: '2', found: '0'