QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#108051	#5463. Range Closest Pair of Points Query	xcyle	TL	2701ms	193660kb	C++14	2.5kb	2023-05-23 15:11:21	2023-05-23 15:11:25

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:11:25]
评测

测评结果：TL
用时：2701ms
内存：193660kb

查看

[2023-05-23 15:11:21]
提交

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

源文件, 语言: C++14

詳細信息

Test #1:

score: 100

Accepted

time: 41ms

memory: 187124kb

input:

output:

result:

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

Test #2:

score: 0

Accepted

time: 28ms

memory: 187096kb

input:

output:

result:

ok 1 number(s): "0"

Test #3:

score: 0

Accepted

time: 42ms

memory: 187144kb

input:

2 1
1 100000000
100000000 1
1 2

output:

19999999600000002

result:

ok 1 number(s): "19999999600000002"

Test #4:

score: 0

Accepted

time: 271ms

memory: 192872kb

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: 2701ms

memory: 193660kb

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