QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#123050 | #5463. Range Closest Pair of Points Query | c20230537 | TL | 6373ms | 263576kb | C++14 | 1.8kb | 2023-07-11 17:36:52 | 2023-07-11 17:37:10 |
Judging History
answer
#include<bits/stdc++.h>
#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 push_back
const ll N=5e6+10;
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace __gnu_cxx;
using namespace __gnu_pbds;
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;
scanf("%lld%lld",&n,&q);
blo=sqrt(n);
For(i,1,n){
scanf("%lld%lld",&X[i],&Y[i]);
b[i]=(i-1)/blo+1;
ma[i]=mb[i]=1e18;
}
For(i,1,q){
ll l,r;
scanf("%lld%lld",&l,&r);
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;
vector<ll>tmp;
for(ll l:a[vis[j][ID]]){
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[vis[j][ID]]=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: 25ms
memory: 247424kb
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: 28ms
memory: 249412kb
input:
2 1 1 1 1 1 1 2
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 35ms
memory: 247368kb
input:
2 1 1 100000000 100000000 1 1 2
output:
19999999600000002
result:
ok 1 number(s): "19999999600000002"
Test #4:
score: 0
Accepted
time: 143ms
memory: 259120kb
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: 828ms
memory: 259524kb
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: 6373ms
memory: 263576kb
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...