QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#123044 | #5463. Range Closest Pair of Points Query | c20230537 | ML | 0ms | 0kb | C++14 | 1.8kb | 2023-07-11 17:34:51 | 2023-07-11 17:34:52 |
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[N];
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: 0
Memory Limit Exceeded
input:
5 5 2 4 1 1 3 3 5 1 4 2 1 5 2 3 2 4 3 5 1 3