QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#122560#5463. Range Closest Pair of Points QueryEnder32kRE 3ms16048kbC++202.5kb2023-07-10 19:14:012023-07-10 19:14:03

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-10 19:14:03]
  • 评测
  • 测评结果:RE
  • 用时:3ms
  • 内存:16048kb
  • [2023-07-10 19:14:01]
  • 提交

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

output:


result: