QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#142731 | #5463. Range Closest Pair of Points Query | TadijaSebez | WA | 3ms | 12112kb | C++14 | 2.7kb | 2023-08-19 18:42:42 | 2023-08-19 18:42:44 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int N=250050;
int x[N],y[N],l[N],r[N];
ll ans[N];
int n,q;
ll sq(int x){
return (ll)x*x;
}
ll Dist(int i,int j){
return sq(x[i]-x[j])+sq(y[i]-y[j]);
}
const ll inf=1e18;
const ll H=1e9;
const int L=25;
vector<int> last[L];
int ptr[L];
vector<int> Qs[N];
vector<pair<int,int>> all[L];
vector<vector<int>> nxt[L];
const int S=500;
const int B=N/S+5;
ll mn[L][N],mnBlock[L][B];
void Set(int lvl,int i,ll x){
mn[lvl][i]=min(mn[lvl][i],x);
mnBlock[lvl][i/S]=min(mnBlock[lvl][i/S],x);
}
ll Get(int lvl,int l,int r){
ll ans=inf;
int L=l/S;
int R=r/S;
if(L==R){
for(int i=l;i<=r;i++){
ans=min(ans,mn[lvl][i]);
}
}else{
for(int i=l;i<(L+1)*S;i++){
ans=min(ans,mn[lvl][i]);
}
for(int i=L+1;i<R;i++){
ans=min(ans,mnBlock[lvl][i]);
}
for(int i=R*S;i<=r;i++){
ans=min(ans,mn[lvl][i]);
}
}
return ans;
}
int main(){
scanf("%i %i",&n,&q);
for(int i=1;i<=n;i++){
scanf("%i %i",&x[i],&y[i]);
}
for(int i=1;i<=q;i++){
scanf("%i %i",&l[i],&r[i]);
Qs[r[i]].pb(i);
}
for(int j=0;j<L;j++){
for(int i=1;i<=n;i++){
mn[j][i]=inf;
mnBlock[j][i/S]=inf;
}
}
for(int i=1;i<=n;i++){
for(int j=0;j<L;j++){
int X=x[i]>>j;
int Y=y[i]>>j;
all[j].pb({X,Y});
}
}
for(int j=0;j<L;j++){
sort(all[j].begin(),all[j].end());
all[j].erase(unique(all[j].begin(),all[j].end()),all[j].end());
for(int i=0;i<all[j].size();i++){
int X=all[j][i].first;
int Y=all[j][i].second;
vector<int> go;
for(int dx=-3;dx<=3;dx++){
for(int dy=-3;dy<=3;dy++){
if(dx==0 && dy==0)continue;
if(abs(dx)==3 && abs(dy)==3)continue;
int nx=X+dx;
int ny=Y+dy;
int k=lower_bound(all[j].begin(),all[j].end(),make_pair(nx,ny))-all[j].begin();
if(k<all[j].size() && all[j][k].first==nx && all[j][k].second==ny){
go.pb(k);
}
}
}
nxt[j].pb(go);
}
last[j].resize(all[j].size());
}
for(int i=1;i<=n;i++){
for(int j=0;j<L;j++){
int X=x[i]>>j;
int Y=y[i]>>j;
int k=lower_bound(all[j].begin(),all[j].end(),make_pair(X,Y))-all[j].begin();
if(last[j][k]){
ptr[j]=max(ptr[j],last[j][k]+1);
}
last[j][k]=i;
auto Try=[&](int p){
if(p!=-1 && p!=k){
int idx=last[j][p];
ll dist=Dist(i,idx);
Set(j,idx,dist);
}
};
for(int o=0;o<nxt[j][k].size();o++){
Try(nxt[j][k][o]);
}
}
for(int qi:Qs[i]){
int lvl=-1;
for(int j=L-1;~j;j--){
if(ptr[j]<=l[qi]){
lvl=j;
break;
}
}
if(lvl==-1)ans[qi]=0;
else{
ans[qi]=Get(lvl,l[qi],r[qi]);
}
}
}
for(int i=1;i<=q;i++)printf("%lld\n",ans[i]);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 12112kb
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: 3ms
memory: 12100kb
input:
2 1 1 1 1 1 1 2
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: -100
Wrong Answer
time: 1ms
memory: 10064kb
input:
2 1 1 100000000 100000000 1 1 2
output:
1000000000000000000
result:
wrong answer 1st numbers differ - expected: '19999999600000002', found: '1000000000000000000'