QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#122630#5463. Range Closest Pair of Points QueryEnder32kAC ✓5995ms473088kbC++204.1kb2023-07-10 20:46:362023-07-10 20:46:38

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 20:46:38]
  • 评测
  • 测评结果:AC
  • 用时:5995ms
  • 内存:473088kb
  • [2023-07-10 20:46:36]
  • 提交

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}, {-1, 1}, {1, 1}};
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(id[l], k), Y(id[l], k))].se, sx = X(id[l], k), sy = Y(id[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: 100
Accepted
time: 1ms
memory: 24092kb

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: 5ms
memory: 24096kb

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: 24048kb

input:

2 1
1 100000000
100000000 1
1 2

output:

19999999600000002

result:

ok 1 number(s): "19999999600000002"

Test #4:

score: 0
Accepted
time: 137ms
memory: 49040kb

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: 175ms
memory: 49832kb

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: 222ms
memory: 49928kb

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: 0
Accepted
time: 322ms
memory: 49888kb

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...

output:

3576676
1219565
93925
2336788
8872
68
137
842657
137
8560936
13914025
28521
88362
8872
8872
52996
12869
86297
68
8137625
93925
12869
86297
8872
8872
8872
47888
8872
12869
107860
12869
59536
59536
425540
12869
59536
8872
93925
117225
137
137
52996
68
52996
137
8872
68
12869
137
68
86297
1514
159700
6...

result:

ok 250000 numbers

Test #8:

score: 0
Accepted
time: 401ms
memory: 49256kb

input:

20000 250000
65468917 46637638
46041830 58072288
95596278 49154795
57837493 40861050
21328886 69542502
7729300 7126264
2317013 48080367
75669670 20165373
93996778 88884044
8523082 62327896
123901 11925128
71901024 73104267
94991893 98591670
53591520 11543761
76785613 86286274
64694742 89591932
75687...

output:

185588005
3282196826
141969393
25769005
141969393
185588005
576346153849
141969393
141969393
185588005
141969393
141969393
141969393
141969393
135584833
141969393
141969393
485404589
1182793
1182793
35224007589
135584833
185588005
931246420
185588005
25769005
375240717
141969393
2245310308
239709665...

result:

ok 250000 numbers

Test #9:

score: 0
Accepted
time: 1231ms
memory: 162960kb

input:

250000 250000
1 2
1 1
3 2
3 3
1 2
3 2
1 2
1 3
3 1
2 1
1 3
2 3
3 3
1 3
3 1
3 1
1 3
2 1
1 2
1 1
1 2
2 2
1 2
1 2
1 3
3 3
1 1
3 2
1 2
2 2
1 1
2 3
3 2
2 1
3 3
2 1
2 3
3 1
2 3
3 2
2 1
1 1
3 2
1 2
1 3
3 1
2 3
2 1
1 2
1 1
1 2
3 3
1 2
2 2
3 1
3 1
3 1
1 2
2 2
1 1
3 3
1 3
1 3
1 2
1 2
3 1
3 2
1 2
2 2
1 2
1 1
2 ...

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 #10:

score: 0
Accepted
time: 2421ms
memory: 384648kb

input:

250000 250000
65 333
64 141
52 164
104 499
329 292
187 279
178 394
92 488
223 487
457 262
355 475
466 223
450 293
397 22
390 379
257 389
339 162
228 267
446 78
116 3
28 400
63 319
255 491
459 301
340 321
183 340
469 6
288 268
383 446
456 13
478 383
109 79
142 317
132 219
168 347
30 398
59 453
192 33...

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
1
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
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 250000 numbers

Test #11:

score: 0
Accepted
time: 3333ms
memory: 384560kb

input:

250000 250000
5939 214
4869 2285
3576 8124
1179 6365
863 9874
6034 7110
9688 5453
1631 1975
7330 8868
1035 8771
9222 9417
7858 1642
3145 4403
8553 6105
8162 2232
2192 4946
5925 8017
1235 5374
6897 5409
8507 8625
7239 4621
5581 4870
4979 1749
35 1282
9138 5489
1030 8851
4444 905
5808 4770
348 7535
16...

output:

1
4
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
2
0
0
0
2
0
0
0
0
0
0
0
0
0
0
0
0
25
1
0
0
0
1
0
0
0
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
2
0
2
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
1
0
0
0
0
0
0
0
0
0
0
0
1
0
4
0
0
0
1
21925
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 250000 numbers

Test #12:

score: 0
Accepted
time: 5995ms
memory: 304892kb

input:

250000 250000
7455187 75182576
14834779 53171998
80916167 45846874
44479602 88587946
22419247 21232863
45054521 14420458
26938419 38366452
40688894 64933635
58825078 27729802
43992064 49857990
80761962 17266078
67198634 69525730
78961694 90909521
86333066 79243240
75184949 63327693
20070526 51545836...

output:

345163988
17297
17297
17297
3342826
2692082
9929385
17297
17297
8796836
17297
1024786
17297
17297
11911909
17297
17297
1518912
39645
3342826
623969
17297
17297
9929385
17297
17297
1931549
346277845
17297
17297
11911909
117753730
17297
5756500
623969
1024786
17297
17297
4290746
17297
17297
623969
172...

result:

ok 250000 numbers

Test #13:

score: 0
Accepted
time: 5976ms
memory: 304824kb

input:

250000 250000
46988183 58848304
68248752 17909655
83617101 6540168
35239739 61188742
53626925 43849602
93050637 37107186
81895363 18264817
49186829 46896179
432608 14970834
27450067 64324424
95545626 36896275
99221358 60404199
53496911 74842046
75080552 5484539
24301428 65640142
96567779 65503273
98...

output:

364165
364165
364165
364165
1118420
364165
2875970
364165
364165
18782189
364165
2443444
2443444
364165
364165
2443444
477485
4069129
4832930
6161897
26896946
364165
26896946
2875970
1028485
16319272
1028485
364165
10848521
364165
893349
8344033
1861925
893349
16319272
2875970
2443444
364165
1028485...

result:

ok 250000 numbers

Test #14:

score: 0
Accepted
time: 5990ms
memory: 304884kb

input:

250000 250000
91248546 19112361
80003885 9173894
78946509 40597624
69292429 19443411
62836211 54539297
21113442 50348948
79804335 68234343
72628821 86879420
57634006 80551531
56031660 58204680
64883168 19157561
57708639 65267544
16502324 51487377
52951273 64713455
36315517 95949044
53263309 72456798...

output:

173585
1749061
17137028
173585
173585
173585
173585
173585
829306
245785
173585
3192869
173585
1100852
39267488
173585
173585
245785
14222466
245785
173585
173585
173585
173585
2558933
173585
173585
27213905
829306
353040509
1100852
173585
173585
20949364
1100852
173585
173585
173585
11259905
919450...

result:

ok 250000 numbers

Test #15:

score: 0
Accepted
time: 2028ms
memory: 280652kb

input:

240032 250000
50000000 50000000
50002262 76010790
50001271 86525300
98641920 50000129
50002536 73103650
33803461 50003187
50001627 17251861
84626110 50001450
14694851 50001386
50002865 30387041
50002785 29538241
3543741 50000335
50002609 72329120
10652441 50001005
69740280 50002853
50000834 8838131
...

output:

112470002
112470002
112470002
112470002
112470002
112470002
112470002
112470002
112470002
112470002
112470002
112470002
112470002
112470002
112470002
112470002
112470002
112470002
112470002
112470002
112470002
112470002
112470002
112470002
112470002
112470002
112470002
112470002
112470002
112470002
...

result:

ok 250000 numbers

Test #16:

score: 0
Accepted
time: 2051ms
memory: 280664kb

input:

240032 250000
50000000 50000000
35893631 50003384
39734451 50003746
87851550 50001146
22238561 50002097
22864551 50002156
50000020 201591
24784961 50002337
50001288 13655071
50003130 66801310
33485161 50003157
4360711 50000412
16731971 50001578
11214771 50001058
50002790 70408710
50002188 23204071
5...

output:

112470002
112470002
112470002
112470002
112470002
112470002
112470002
112470002
112470002
112470002
112470002
112470002
112470002
112470002
112470002
112470002
112470002
112470002
112470002
112470002
112470002
112470002
112470002
112470002
112470002
112470002
112470002
112470002
112470002
112470002
...

result:

ok 250000 numbers

Test #17:

score: 0
Accepted
time: 1527ms
memory: 287448kb

input:

250000 250000
50000000 50000000
50000001 49999999
50000002 49999998
50000003 49999997
50000004 49999996
50000005 49999995
50000006 49999994
50000007 49999993
50000008 49999992
50000009 49999991
50000010 49999990
50000011 49999989
50000012 49999988
50000013 49999987
50000014 49999986
50000015 4999998...

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 #18:

score: 0
Accepted
time: 2418ms
memory: 473088kb

input:

250000 250000
50000000 50000000
50000001 49999999
50000002 49999998
50000003 49999997
50000004 49999996
50000005 49999995
50000006 49999994
50000007 49999993
50000008 49999992
50000009 49999991
50000010 49999990
50000011 49999989
50000012 49999988
50000013 49999987
50000014 49999986
50000015 4999998...

output:

1
2
2
1
2
2
2
2
2
2
1
2
2
2
1
2
2
2
2
2
1
2
1
2
2
2
2
2
2
2
2
1
2
2
1
2
1
1
2
2
1
2
2
2
2
2
2
2
2
2
2
2
1
2
2
2
2
1
2
2
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
2
2
1
2
2
1
1
2
2
2
1
2
2
2
2
2
2
1
2
2
2
2
2
1
2
2
2
1
1
2
2
2
2
2
2
2
1
2
1
1
2
1
2
2
2
1
2
2
2
2
2
1
2
1
1
2
1
2
2
2
2
1
1
1
2
2
1
2
2
2
1
2
1
1
...

result:

ok 250000 numbers