QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#122561#5463. Range Closest Pair of Points QueryEnder32kWA 139ms22836kbC++202.5kb2023-07-10 19:14:292023-07-10 19:14:32

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-10 19:14:32]
  • 评测
  • 测评结果:WA
  • 用时:139ms
  • 内存:22836kb
  • [2023-07-10 19:14:29]
  • 提交

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;

mt19937 rnd(time(0));
const int N = 2.5e5 + 250;
const int P = 998244353;
const ll inf = 2e18;
const int W = 1000;
int n, m, x[N], y[N], id[N], rid[N];
double t[N];
vector<pi> qr[N];
ll ans[N];

ll min(ll i, ll j) { return i > j ? j : i; }
ll tr[N];
int lb(int i) { return i & (-i); }
void mdf(int p, ll q) { for (int i = p; i; i -= lb(i)) tr[i] = min(tr[i], q); }
ll qry(int p) { ll res = inf; for (int i = p; i <= n; i += lb(i)) res = min(res, tr[i]); return res; }

int main() {
	n = rd(), m = rd();
	for (int i = 1; i <= n; i++) x[i] = rd(), y[i] = rd(), id[i] = i, tr[i] = inf;
	for (int i = 1, l, r; i <= m; i++) l = rd(), r = rd(), qr[r].pb(mp(l, i));
	double tp = 1. * (rnd() % P) / P * 2 * acos(-1), ta = cos(tp), tb = sin(tp);
	for (int i = 1; i <= n; i++) t[i] = x[i] * ta + y[i] * tb;
	sort(id + 1, id + n + 1, [](int &i, int &j) { return t[i] < t[j]; });
	for (int i = 1; i <= n; i++) rid[id[i]] = i;
	for (int r = 1; r <= n; r++) {
		for (int l = max(1, r - W); l < r; l++) 
			mdf(l, 1ll * (x[l] - x[r]) * (x[l] - x[r]) + 1ll * (y[l] - y[r]) * (y[l] - y[r]));
		for (int l = max(1, rid[r] - W); l <= min(rid[l] + W, n); l++) 
			if (id[l] < r) mdf(id[l], 1ll * (x[id[l]] - x[r]) * (x[id[l]] - x[r]) + 1ll * (y[id[l]] - y[r]) * (y[id[l]] - y[r]));
		for (pi p : qr[r]) ans[p.se] = qry(p.fi);
	}
	for (int i = 1; i <= m; i++)
		wr(ans[i]), puts("");
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 17924kb

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: 2ms
memory: 18032kb

input:

2 1
1 1
1 1
1 2

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 3ms
memory: 18052kb

input:

2 1
1 100000000
100000000 1
1 2

output:

19999999600000002

result:

ok 1 number(s): "19999999600000002"

Test #4:

score: 0
Accepted
time: 131ms
memory: 22736kb

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: 139ms
memory: 22776kb

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
Wrong Answer
time: 134ms
memory: 22836kb

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
1
0
0
0
0
0
0
0
0
0
0
45
1
0
1
0
0
1
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
1
0
0
0
0
0
0
0
0
0
0
0
1
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:

wrong answer 6th numbers differ - expected: '0', found: '1'