QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#142712 | #5463. Range Closest Pair of Points Query | TadijaSebez | WA | 172ms | 27264kb | C++14 | 3.1kb | 2023-08-19 18:31:34 | 2023-08-19 18:31:37 |
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=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'