QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#80397#5463. Range Closest Pair of Points Query_UMqwq_WA 230ms213820kbC++202.6kb2023-02-23 16:25:032023-02-23 16:25:09

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-23 16:25:09]
  • 评测
  • 测评结果:WA
  • 用时:230ms
  • 内存:213820kb
  • [2023-02-23 16:25:03]
  • 提交

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'