QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#142712#5463. Range Closest Pair of Points QueryTadijaSebezWA 172ms27264kbC++143.1kb2023-08-19 18:31:342023-08-19 18:31:37

Judging History

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

  • [2023-08-19 18:31:37]
  • 评测
  • 测评结果:WA
  • 用时:172ms
  • 内存:27264kb
  • [2023-08-19 18:31:34]
  • 提交

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=27;
//unordered_map<ll,int> last[L];
vector<int> last[L];
int ptr[L];
vector<int> Qs[N];

vector<pair<int,int>> all[L];
vector<array<int,8>> 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 mv[8][2]={{0,1},{0,-1},{1,0},{-1,0},{-1,-1},{-1,1},{1,1},{1,-1}};
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;
			array<int,8> go;
			for(int z=0;z<8;z++){
				int nx=X+mv[z][0];
				int ny=Y+mv[z][1];
				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[z]=k;
				}else go[z]=-1;
			}
			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);
				}
			};
			auto Consider=[&](int p){
				if(p!=-1){
					Try(p);
					for(int o=0;o<8;o++){
						Try(nxt[j][p][o]);
					}
				}
			};
			for(int o=0;o<8;o++){
				Consider(nxt[j][k][o]);
			}
			/*for(int dx=-2;dx<=2;dx++){
				for(int dy=-2;dy<=2;dy++){
					if(dx==0 && dy==0)continue;
					if(last[j].count((X+dx)*H+(Y+dy))){
						int idx=last[j][(X+dx)*H+(Y+dy)];
						ll dist=Dist(i,idx);
						Set(j,idx,dist);
					}
				}
			}*/
		}
		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: 11480kb

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: 1ms
memory: 9944kb

input:

2 1
1 1
1 1
1 2

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 1ms
memory: 9772kb

input:

2 1
1 100000000
100000000 1
1 2

output:

19999999600000002

result:

ok 1 number(s): "19999999600000002"

Test #4:

score: 0
Accepted
time: 72ms
memory: 24824kb

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: 110ms
memory: 25200kb

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: -100
Wrong Answer
time: 172ms
memory: 27264kb

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:

wrong answer 602nd numbers differ - expected: '9', found: '10'