QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#108058	#5463. Range Closest Pair of Points Query	xcyle	TL	3130ms	193720kb	C++14	2.5kb	2023-05-23 15:17:24	2023-05-23 15:17:26

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-05-23 15:17:26]
评测

测评结果：TL
用时：3130ms
内存：193720kb

查看

[2023-05-23 15:17:24]
提交

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;
				assert(tmp.size() <= 4);
			}
			lim[j + 1] = max(lim[j + 1], lim[j]);
			if(!f[j][H(bx, by)]) f[j][H(bx, by)] = ++tot;
			if(!j) buc[f[j][H(bx, by)]].clear();
			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;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 70ms

memory: 187068kb

input:

output:

result:

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

Test #2:

score: 0

Accepted

time: 48ms

memory: 187096kb

input:

output:

result:

ok 1 number(s): "0"

Test #3:

score: 0

Accepted

time: 36ms

memory: 187072kb

input:

2 1
1 100000000
100000000 1
1 2

output:

19999999600000002

result:

ok 1 number(s): "19999999600000002"

Test #4:

score: 0

Accepted

time: 182ms

memory: 192864kb

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

Accepted

time: 3130ms

memory: 193720kb

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:

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