QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#122508 | #5463. Range Closest Pair of Points Query | hxhhxh | WA | 242ms | 31216kb | C++14 | 1.6kb | 2023-07-10 17:25:10 | 2023-07-10 17:25:13 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,pos[400005],B=512,ans[400005];
struct SEG{
int r[400005],t[555];
void init(){
memset(r,0x3f,sizeof(r));
memset(t,0x3f,sizeof(t));
}
void cg(int x,int v){
t[x>>9]=min(t[x>>9],v);
r[x]=min(r[x],v);
}
int que(int L,int R){
int res=1e18;
for(int i=L;i<=L+B&&i<=R;i++) res=min(res,r[i]);
for(int i=R;i>=R-B&&i>=L;i--) res=min(res,r[i]);
for(int i=(L>>9)+1;i<(R>>9);i++) res=min(res,t[i]);
return res;
}
}T;
struct st{
int x,y,id;
}a[400005];
struct qt{
int l,r;
}c[400005];
vector<int>r[400005];
set<int>s;
int dis(int x,int y){
return (a[x].x-a[y].x)*(a[x].x-a[y].x)+(a[x].y-a[y].y)*(a[x].y-a[y].y);
}
signed main(){
cin>>n>>q;
for(int i=1;i<=n;i++) scanf("%lld %lld",&a[i].x,&a[i].y),a[i].id=i;
sort(a+1,a+n+1,[&](st l,st rr){return (l.x*l.x+l.y*l.y)<(rr.x*rr.x+rr.y*rr.y);});
for(int i=1;i<=n;i++) pos[a[i].id]=i;
for(int i=1;i<=q;i++){
scanf("%lld %lld",&c[i].l,&c[i].r);
r[c[i].r].push_back(i);
}
T.init();
for(int _=1;_<=n;_++){
int i=pos[_],rt=0;
// cout<<_<<"\t"<<i<<endl;
auto o=s.insert(i).first;
if(o!=s.begin()){
for(auto t=prev(o);t!=s.begin()&&rt<=50;t--) T.cg(a[*t].id,dis(i,*t)),rt++;//,cout<<(*t)<<",";
T.cg(a[*s.begin()].id,dis(i,*s.begin()));
}
// cout<<*s.begin()<<";";
rt=0;
for(auto t=next(o);t!=s.end()&&rt<=50;t++) T.cg(a[*t].id,dis(i,*t)),rt++;//,cout<<(*t)<<",";
// cout<<endl;
for(int j:r[_]) ans[j]=T.que(c[j].l,c[j].r);
}
for(int i=1;i<=q;i++) cout<<ans[i]<<"\n";
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 24752kb
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: 21680kb
input:
2 1 1 1 1 1 1 2
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 4ms
memory: 21504kb
input:
2 1 1 100000000 100000000 1 1 2
output:
19999999600000002
result:
ok 1 number(s): "19999999600000002"
Test #4:
score: -100
Wrong Answer
time: 242ms
memory: 31216kb
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 423rd numbers differ - expected: '1', found: '1000000000000000000'