QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#150375 | #5463. Range Closest Pair of Points Query | bai_hong | WA | 3ms | 21212kb | C++14 | 2.4kb | 2023-08-25 16:42:28 | 2023-08-25 16:42:29 |
Judging History
answer
/*
Sakurajima Mai,
Eriri Spencer,
Izumi Sagiri,
Keqing,
Hu tao,
Ganyu
say,"With our sincere wishes to HHX: never to debug code"
*/
#include<bits/stdc++.h>
#define R register
#define ll long long
#define random mt19937
const int QWQ=250005;
using namespace std;
inline int read(){
int x=0,f=1; char ch=getchar();
while (!isdigit(ch)){ if (ch=='-') f=-1; ch=getchar(); }
while (isdigit(ch)){ x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
return x*f;
}
int n,q,id[QWQ],pos[QWQ]; ll res[QWQ];
pair<int,int> din[QWQ]; double com[QWQ];
vector<pair<int,int> > ques[QWQ];
inline int max(const int &x,const int &y){ return x>y ? x:y; }
inline int min(const int &x,const int &y){ return x<y ? x:y; }
inline ll powr(const int &x){ return (ll)x*x; }
inline ll getlen(const int &i,const int &j){
return powr(din[i].first-din[j].first)+powr(din[i].second-din[j].second);
}
inline bool cmp(const int &i,const int &j){ return com[i]<com[j]; }
namespace work{
const int inf=0x3f3f3f3f3f3f3f3f;
const int block=500;
ll ta[QWQ],tb[QWQ];
inline void init(){
for (R int i=0;i<QWQ;i++)
ta[i]=tb[i]=inf;
}
inline void add(int x,ll d){
ta[x]=min(ta[x],d);
tb[x/block]=min(tb[x/block],d);
}
inline ll ask(int l,int r){
ll res=inf; int ls=l/block,rs=r/block;
if (ls==rs){
for (R int i=l;i<=r;i++)
res=min(res,ta[i]);
return res;
} for (R int i=l;i<(ls+1)*block;i++) res=min(res,ta[i]);
for (R int i=rs*block;i<=r;i++) res=min(res,ta[i]);
for (R int i=ls+1;i<rs;i++) res=min(res,tb[i]);
return res;
}
}
signed main(){
n=read(),q=read();
random rand(10086);
for (R int i=1;i<=n;i++)
din[i].first=read(),din[i].second=read();
for (R int i=1;i<=q;i++){
int l=read(),r=read();
ques[r].push_back({l,i});
}
double rl=(rand()%100000000+1)/100000000.0*2*acos(-1.0);
// double rl=1145141919810ll;
double siin=sin(rl),coos=cos(rl);
for (R int i=1;i<=n;i++)
com[i]=din[i].first*coos-din[i].second*siin,id[i]=i;
sort(id+1,id+1+n,cmp);
for (R int i=1;i<=n;i++)
pos[id[i]]=i;
work::init();
for (R int i=1;i<=n;i++){
for (R int j=max(1,i-1000);j<i;j++)
work::add(j,getlen(j,i));
for (R int j=max(1,pos[i]-1000);j<=min(n,pos[i]+1000);j++)
if (id[j]<i) work::add(id[j],getlen(id[j],i));
for (auto j:ques[i]) res[j.second]=work::ask(j.first,i);
} for (R int i=1;i<=q;i++) printf("%lld\n",res[i]);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 21064kb
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: 20796kb
input:
2 1 1 1 1 1 1 2
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: -100
Wrong Answer
time: 3ms
memory: 21212kb
input:
2 1 1 100000000 100000000 1 1 2
output:
1061109567
result:
wrong answer 1st numbers differ - expected: '19999999600000002', found: '1061109567'