QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#123082#5463. Range Closest Pair of Points Queryc20230537TL 5096ms264812kbC++142.1kb2023-07-11 18:23:572023-07-11 18:23:59

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-11 18:23:59]
  • 评测
  • 测评结果:TL
  • 用时:5096ms
  • 内存:264812kb
  • [2023-07-11 18:23:57]
  • 提交

answer

#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#define ll long long
#define For(i,a,b) for(ll i=(a);i<=(b);++i)
#define Rep(i,a,b) for(ll i=(a);i>=(b);--i)
#define Yes printf("Yes\n")
#define No printf("No\n")
#define pb emplace_back
const ll N=5e6+10;
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;

char *p1,*p2,buf[100000];
#define nc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
int read(){int x=0,f=1;char ch=nc();while(ch<48||ch>57){if(ch=='-')f=-1;ch=nc();}while(ch>=48&&ch<=57)x=x*10+ch-48,ch=nc();return x*f;}

ll nt[9][2]={0,0,0,-1,-1,0,0,1,1,0,1,-1,-1,1,-1,-1,1,1};
ll n,q;
ll X[N],Y[N];
vector<pair<ll,ll>>query[N];
vector<ll>a[N];
ll blo,b[N],ma[N],mb[N];
ll ans[N];

ll num;
gp_hash_table<ll,ll>vis[35];

ll ask(ll l,ll r){
	ll ans=1e18;
	if(b[l]==b[r]){
		For(i,l,r)ans=min(ans,ma[i]);
	}else{
		for(ll i=l;b[i]==b[l];++i)ans=min(ans,ma[i]);
		For(i,b[l]+1,b[r])ans=min(ans,mb[i]);
	}
	return ans;
}

void solve(){
	
	ll V=1e8;
	n=read(),q=read();
	blo=sqrt(n);
	For(i,1,n){
		X[i]=read(),Y[i]=read();
		b[i]=(i-1)/blo+1;
		ma[i]=mb[i]=1e18;
	}
	For(i,1,q){
		ll l,r;
		l=read(),r=read();
		query[r].pb(l,i);
		ans[i]=1e18;
	}
	For(r,1,n){
		for(ll j=1;(1<<j)<=V;++j){
			ll x=X[r]>>j,y=Y[r]>>j;
			ll t=V>>j;
			ll id=(x<<32)|y;
			if(vis[j].find(id)==vis[j].end())vis[j][id]=++num;
			For(k,0,8){
				ll xx=x+nt[k][0],yy=y+nt[k][1];
				ll ID=(xx<<32)|yy;
				if(xx<0||xx>t||yy<0||yy>t)continue;
				if(vis[j].find(ID)==vis[j].end())continue;
				ll SB=vis[j][ID];
				vector<ll>tmp;
				for(ll l:a[SB]){
					ll dis=(X[r]-X[l])*(X[r]-X[l])+(Y[r]-Y[l])*(Y[r]-Y[l]);
					ma[l]=min(ma[l],dis),mb[b[l]]=min(mb[b[l]],dis);
					if(dis>=(1ll<<j+j-2))tmp.pb(l);
				}
				if(!k)tmp.pb(r);
				a[SB]=tmp;
			}
		}
		for(auto &[x,y]:query[r])ans[y]=ask(x,r);
	}
	For(i,1,q)printf("%lld\n",ans[i]);
	
}
int main(){
	int T=1;
//	scanf("%d",&T);
	while(T--)solve();
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 27ms
memory: 249396kb

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: 39ms
memory: 249356kb

input:

2 1
1 1
1 1
1 2

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 28ms
memory: 247304kb

input:

2 1
1 100000000
100000000 1
1 2

output:

19999999600000002

result:

ok 1 number(s): "19999999600000002"

Test #4:

score: 0
Accepted
time: 112ms
memory: 258896kb

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:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 250000 numbers

Test #5:

score: 0
Accepted
time: 566ms
memory: 260068kb

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:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 250000 numbers

Test #6:

score: 0
Accepted
time: 5096ms
memory: 264812kb

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

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
45
1
0
1
0
0
0
2
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
0
0
2
0
0
0
0
0
0
0
0
0
0
52
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
2
0
0
0
0
5
0
0
0
0
0
1
0
0
0
1
1
0
0
0
2
0
0
0
0
0
0
...

result:

ok 250000 numbers

Test #7:

score: -100
Time Limit Exceeded

input:

20000 250000
193144 901630
894860 3728
802840 155641
625273 792794
433205 942335
223506 874548
425235 550629
341169 950916
49296 305542
709463 512381
9742 994078
106664 845553
38691 373010
184728 331946
344567 438182
854583 291040
94405 555036
56330 494420
928479 123077
796593 798314
300374 490072
2...

output:


result: