QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#108047 | #5463. Range Closest Pair of Points Query | xcyle | TL | 8808ms | 29016kb | C++14 | 2.4kb | 2023-05-23 15:07:46 | 2023-05-23 15:07:48 |
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];
__gnu_pbds::gp_hash_table<ll, vector<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: 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));
}
}
f[j][H(tx, ty)] = tmp;
}
lim[j + 1] = max(lim[j + 1], lim[j]);
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 5ms
memory: 11320kb
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: 1ms
memory: 11296kb
input:
2 1 1 1 1 1 1 2
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 4ms
memory: 11452kb
input:
2 1 1 100000000 100000000 1 1 2
output:
19999999600000002
result:
ok 1 number(s): "19999999600000002"
Test #4:
score: 0
Accepted
time: 225ms
memory: 17152kb
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: 2265ms
memory: 18964kb
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: 0
Accepted
time: 8808ms
memory: 29016kb
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...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 45 1 0 1 0 0 0 2 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 4 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 52 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 5 0 0 0 0 0 1 0 0 0 1 1 0 0 0 2 0 0 0 0 0 0 ...
result:
ok 250000 numbers
Test #7:
score: -100
Time Limit Exceeded
input:
20000 250000 193144 901630 894860 3728 802840 155641 625273 792794 433205 942335 223506 874548 425235 550629 341169 950916 49296 305542 709463 512381 9742 994078 106664 845553 38691 373010 184728 331946 344567 438182 854583 291040 94405 555036 56330 494420 928479 123077 796593 798314 300374 490072 2...