QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#186146	#5463. Range Closest Pair of Points Query	APJifengc	WA	208ms	90756kb	C++14	3.0kb	2023-09-23 09:45:54	2023-09-23 09:45:55

Judging History

你现在查看的是最新测评结果

[2023-09-23 09:45:55]
评测

测评结果：WA
用时：208ms
内存：90756kb

查看

[2023-09-23 09:45:54]
提交

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 + 8 && j < r; j++) {
            // printf("(%d, %d)\n", p[i], p[j]);
            if (p[i] < p[j]) pts[p[j]].push_back(p[i]);
            else pts[p[i]].push_back(p[j]);
        }
    };
    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;
}

源文件, 语言: C++14

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 26272kb

input:

output:

result:

ok 5 number(s): "2 8 8 2 2"

Test #2:

score: 0

Accepted

time: 0ms

memory: 26316kb

input:

output:

result:

ok 1 number(s): "0"

Test #3:

score: 0

Accepted

time: 0ms

memory: 28640kb

input:

2 1
1 100000000
100000000 1
1 2

output:

19999999600000002

result:

ok 1 number(s): "19999999600000002"

Test #4:

score: 0

Accepted

time: 172ms

memory: 75100kb

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:

result:

ok 250000 numbers

Test #5:

score: -100

Wrong Answer

time: 208ms

memory: 90756kb

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:

result:

wrong answer 48463rd numbers differ - expected: '125', found: '130'