QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#108034	#5463. Range Closest Pair of Points Query	xcyle	WA	469ms	17792kb	C++14	2.2kb	2023-05-23 14:51:32	2023-05-23 14:51:36

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 14:51:36]
评测

测评结果：WA
用时：469ms
内存：17792kb

查看

[2023-05-23 14:51:32]
提交

answer

/*

_/      _/       _/_/_/      _/      _/    _/           _/_/_/_/_/
 _/    _/      _/      _/     _/    _/     _/           _/
  _/  _/      _/               _/  _/      _/           _/
   _/_/       _/                 _/        _/           _/_/_/_/
  _/  _/      _/                 _/        _/           _/
 _/    _/      _/      _/        _/        _/           _/
_/      _/       _/_/_/          _/        _/_/_/_/_/   _/_/_/_/_/

*/
#include <bits/stdc++.h>
#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];
map<pii, vector<int> > f[30];
ll t[maxn], ans[maxn];
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, 27) {
			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(mp(tx, ty)) != f[j].end()) {
				vector<int> tmp;
				for (auto x: f[j][mp(tx, ty)]) if(x > lim[j]) {
					tmp.push_back(x);
					if(dis(i, x) < (1ll << (2 * (j + 1)))) {
						lim[j + 1] = max(lim[j + 1], x);
						add(n - x + 1, dis(i, x));
					}
				}
				f[j][mp(tx, ty)] = tmp;
			}
			lim[j + 1] = max(lim[j + 1], lim[j]);
			f[j][mp(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: 2ms

memory: 11316kb

input:

output:

result:

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

Test #2:

score: 0

Accepted

time: 5ms

memory: 11380kb

input:

output:

result:

ok 1 number(s): "0"

Test #3:

score: 0

Accepted

time: 0ms

memory: 12020kb

input:

2 1
1 100000000
100000000 1
1 2

output:

19999999600000002

result:

ok 1 number(s): "19999999600000002"

Test #4:

score: 0

Accepted

time: 469ms

memory: 17028kb

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

memory: 17792kb

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 23952nd numbers differ - expected: '25', found: '29'