QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#108051 | #5463. Range Closest Pair of Points Query | xcyle | TL | 2701ms | 193660kb | C++14 | 2.5kb | 2023-05-23 15:11:21 | 2023-05-23 15:11:25 |
Judging History
answer
/*
_/ _/ _/_/_/ _/ _/ _/ _/_/_/_/_/
_/ _/ _/ _/ _/ _/ _/ _/
_/ _/ _/ _/ _/ _/ _/
_/_/ _/ _/ _/ _/_/_/_/
_/ _/ _/ _/ _/ _/
_/ _/ _/ _/ _/ _/ _/
_/ _/ _/_/_/ _/ _/_/_/_/_/ _/_/_/_/_/
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define lc(x) ((x) << 1)
#define rc(x) ((x) << 1 | 1)
#define ru(i, l, r) for (int i = (l); i <= (r); i++)
#define rd(i, r, l) for (int i = (r); i >= (l); i--)
#define mid ((l + r) >> 1)
#define pii pair<int, int>
#define mp make_pair
#define fi first
#define se second
#define sz(s) (int)s.size()
#define maxn 250005
using namespace std;
int read() {
int x = 0, w = 0; char ch = getchar();
while(!isdigit(ch)) w |= ch == '-', ch = getchar();
while(isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
return w ? -x : x;
}
int n, q, x[maxn], y[maxn], lim[30];
vector<pii> ask[maxn];
vector<int> buc[maxn * 30]; int tot;
__gnu_pbds::gp_hash_table<ll, int> f[30];
ll t[maxn], ans[maxn];
ll H(int x, int y) {
return ((ll)x << 30) + y;
}
ll dis(int a, int b) {
return (ll)(x[a] - x[b]) * (x[a] - x[b]) + (ll)(y[a] - y[b]) * (y[a] - y[b]);
}
void add(int x, ll v) {
for (; x <= n; x += x & (-x)) t[x] = min(t[x], v);
}
ll qry(int x) {
ll res = 1e18;
for (; x; x -= x & (-x)) res = min(res, t[x]);
return res;
}
int main() {
ru(i, 0, maxn - 1) t[i] = 1e18;
n = read(), q = read();
ru(i, 1, n) x[i] = read(), y[i] = read();
ru(i, 1, q) {
int l = read(), r = read();
ask[r].push_back(mp(l, i));
}
ru(i, 1, n) {
ru(j, 0, 28) {
int bx = x[i] >> j, by = y[i] >> j;
ru(tx, bx - 1, bx + 1) ru(ty, by - 1, by + 1) if(f[j].find(H(tx, ty)) != f[j].end()) {
vector<int> tmp;
for (auto x: buc[f[j][H(tx, ty)]]) if(x > lim[j]) {
tmp.push_back(x);
if(dis(i, x) < (1ll << (2 * j))) {
lim[j + 1] = max(lim[j + 1], x);
add(n - x + 1, dis(i, x));
}
}
buc[f[j][H(tx, ty)]] = tmp;
}
lim[j + 1] = max(lim[j + 1], lim[j]);
if(!f[j][H(bx, by)]) f[j][H(bx, by)] = ++tot;
buc[f[j][H(bx, by)]].push_back(i);
}
for (auto x: ask[i]) ans[x.se] = qry(n - x.fi + 1);
}
ru(i, 1, q) printf("%lld\n", ans[i]);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 41ms
memory: 187124kb
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: 28ms
memory: 187096kb
input:
2 1 1 1 1 1 1 2
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 42ms
memory: 187144kb
input:
2 1 1 100000000 100000000 1 1 2
output:
19999999600000002
result:
ok 1 number(s): "19999999600000002"
Test #4:
score: 0
Accepted
time: 271ms
memory: 192872kb
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:
ok 250000 numbers
Test #5:
score: 0
Accepted
time: 2701ms
memory: 193660kb
input:
20000 250000 72 45 72 34 34 10 20 96 79 39 43 5 72 49 56 85 1 72 44 70 73 89 69 76 49 89 57 38 39 9 33 47 22 3 96 41 90 82 25 6 72 92 73 38 53 21 16 88 59 9 54 2 14 6 7 94 99 68 27 82 70 50 81 81 60 81 2 98 33 19 98 9 35 36 49 66 86 7 3 95 32 89 62 42 68 88 65 16 94 6 85 10 51 69 90 36 70 87 13 79 4...
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 10 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 1 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:
ok 250000 numbers
Test #6:
score: -100
Time Limit Exceeded
input:
20000 250000 116 165 150 677 951 676 552 324 267 222 739 755 705 663 235 142 152 714 735 641 414 201 313 663 683 300 403 739 37 521 42 833 553 733 886 449 86 913 55 637 731 932 143 161 500 891 719 79 916 237 431 992 804 210 643 332 165 362 178 332 821 510 762 34 188 83 283 357 743 407 750 487 19 658...