QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#80397 | #5463. Range Closest Pair of Points Query | _UMqwq_ | WA | 230ms | 213820kb | C++20 | 2.6kb | 2023-02-23 16:25:03 | 2023-02-23 16:25:09 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define MAXN 250010
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
using namespace std;
const int S=500;
const int N=100000000;
const int mod=500007;
const int inf=0x3f3f3f3f3f3f3f3f;
int n,Q,ans[MAXN];
int x[MAXN],y[MAXN];
vector<pii>que[MAXN];
struct Block{
int bel[MAXN],lb[MAXN],rb[MAXN],cnt;
int val[MAXN],mx[MAXN];
void init(int n){
cnt=0;
for(int l=1;l<=n;l+=S){
lb[++cnt]=l;rb[cnt]=min(n,l+S-1);
for(int i=lb[cnt];i<=rb[cnt];i++)bel[i]=cnt,val[i]=mx[i]=inf;
}
}
void update(int pos,int v){val[pos]=min(val[pos],v);mx[bel[pos]]=min(mx[bel[pos]],v);}
int query(int l,int r){
int bl=bel[l],br=bel[r];
if(bl==br){
int ret=inf;
for(int i=l;i<=r;i++)ret=min(ret,val[i]);
return ret;
}
int ret=inf;
for(int i=l;i<=rb[bl];i++)ret=min(ret,val[i]);
for(int i=lb[br];i<=r;i++)ret=min(ret,val[i]);
for(int i=bl+1;i<br;i++)ret=min(ret,mx[i]);
return ret;
}
}ds;
struct hshtable{
int head[mod+3],nxt[MAXN],st[MAXN],val[MAXN],cnt;
void clear(){
for(int i=1;i<=cnt;i++)nxt[i]=val[i]=0;
memset(head,0,sizeof(head));cnt=0;
}
void insert(int x,int v){
int key=x%mod;
for(int i=head[key];i;i=nxt[i])
if(st[i]==x)return;
st[++cnt]=x;val[cnt]=v;
nxt[cnt]=head[key];head[key]=cnt;
}
int operator[](int x){
int key=x%mod;
for(int i=head[key];i;i=nxt[i])
if(st[i]==x)return val[i];
return 0;
}
}buc[30];
int get(int x,int y){return x*N+y;}
int dis(int i,int j){return (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);}
vector<int>pos[MAXN<<5];
int ql[MAXN<<5],lmt[30],tot;
void add(int k,int p){
int qx=x[p]/(2<<k),qy=y[p]/(2<<k),id=0;
for(int i=qx-1;i<=qx+1;i++)
for(int j=qy-1;j<=qy+1;j++){
if(i<0||j<0)continue;
int now=buc[k][get(i,j)];if(!now)continue;
for(int t=ql[now];t<(int)pos[now].size();t++){
if(pos[now][t]<=lmt[k]){ql[now]=t;continue;}
int d=dis(pos[now][t],p);ds.update(pos[now][t],d);
// cerr<<pos[now][t]<<' '<<p<<' '<<d<<endl;
if(d<=(1<<k))id=max(id,pos[now][t]);
}
}
lmt[k]=max(lmt[k],id);int now=buc[k][get(qx,qy)];
if(!now)now=++tot,buc[k].insert(get(qx,qy),tot);
pos[now].pb(p);
}
signed main(){
scanf("%lld%lld",&n,&Q);
for(int i=1;i<=n;i++)scanf("%lld%lld",&x[i],&y[i]);
for(int i=1;i<=Q;i++){
int l,r;scanf("%lld%lld",&l,&r);
que[r].pb(mp(l,i));
}ds.init(n);
for(int i=1;i<=n;i++){
for(int k=0;k<=28;k++)add(k,i);
for(auto j:que[i])ans[j.se]=ds.query(j.fi,i);
}
for(int i=1;i<=Q;i++)printf("%lld\n",ans[i]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 45ms
memory: 198780kb
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: 51ms
memory: 198500kb
input:
2 1 1 1 1 1 1 2
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 43ms
memory: 199672kb
input:
2 1 1 100000000 100000000 1 1 2
output:
19999999600000002
result:
ok 1 number(s): "19999999600000002"
Test #4:
score: -100
Wrong Answer
time: 230ms
memory: 213820kb
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:
wrong answer 935th numbers differ - expected: '0', found: '1'