QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#122560 | #5463. Range Closest Pair of Points Query | Ender32k | RE | 3ms | 16048kb | C++20 | 2.5kb | 2023-07-10 19:14:01 | 2023-07-10 19:14:03 |
Judging History
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;
mt19937 rnd(time(0));
const int N = 2e5 + 250;
const int P = 998244353;
const ll inf = 2e18;
const int W = 1000;
int n, m, x[N], y[N], id[N], rid[N];
double t[N];
vector<pi> qr[N];
ll ans[N];
ll min(ll i, ll j) { return i > j ? j : i; }
ll tr[N];
int lb(int i) { return i & (-i); }
void mdf(int p, ll q) { for (int i = p; i; i -= lb(i)) tr[i] = min(tr[i], q); }
ll qry(int p) { ll res = inf; for (int i = p; i <= n; i += lb(i)) res = min(res, tr[i]); return res; }
int main() {
n = rd(), m = rd();
for (int i = 1; i <= n; i++) x[i] = rd(), y[i] = rd(), id[i] = i, tr[i] = inf;
for (int i = 1, l, r; i <= m; i++) l = rd(), r = rd(), qr[r].pb(mp(l, i));
double tp = 1. * (rnd() % P) / P * 2 * acos(-1), ta = cos(tp), tb = sin(tp);
for (int i = 1; i <= n; i++) t[i] = x[i] * ta + y[i] * tb;
sort(id + 1, id + n + 1, [](int &i, int &j) { return t[i] < t[j]; });
for (int i = 1; i <= n; i++) rid[id[i]] = i;
for (int r = 1; r <= n; r++) {
for (int l = max(1, r - W); l < r; l++)
mdf(l, 1ll * (x[l] - x[r]) * (x[l] - x[r]) + 1ll * (y[l] - y[r]) * (y[l] - y[r]));
for (int l = max(1, rid[r] - W); l <= min(rid[l] + W, n); l++)
if (id[l] < r) mdf(id[l], 1ll * (x[id[l]] - x[r]) * (x[id[l]] - x[r]) + 1ll * (y[id[l]] - y[r]) * (y[id[l]] - y[r]));
for (pi p : qr[r]) ans[p.se] = qry(p.fi);
}
for (int i = 1; i <= m; i++)
wr(ans[i]), puts("");
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 14060kb
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: 1ms
memory: 15816kb
input:
2 1 1 1 1 1 1 2
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 3ms
memory: 16048kb
input:
2 1 1 100000000 100000000 1 1 2
output:
19999999600000002
result:
ok 1 number(s): "19999999600000002"
Test #4:
score: -100
Runtime Error
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 ...