QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#108056#5463. Range Closest Pair of Points QueryxcyleRE 42ms187148kbC++142.5kb2023-05-23 15:13:382023-05-23 15:13:39

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:13:39]
  • 评测
  • 测评结果:RE
  • 用时:42ms
  • 内存:187148kb
  • [2023-05-23 15:13:38]
  • 提交

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;
			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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 33ms
memory: 187144kb

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: 42ms
memory: 187148kb

input:

2 1
1 1
1 1
1 2

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 41ms
memory: 187080kb

input:

2 1
1 100000000
100000000 1
1 2

output:

19999999600000002

result:

ok 1 number(s): "19999999600000002"

Test #4:

score: -100
Dangerous Syscalls

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: