QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#122471 | #5463. Range Closest Pair of Points Query | fansizhe | WA | 1434ms | 27220kb | C++23 | 1.7kb | 2023-07-10 15:55:55 | 2023-07-10 15:55:58 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int read(){
int x=0;char c=getchar();
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9')x=x*10+(c^'0'),c=getchar();
return x;
}
#define ll long long
int n,q,B;
const int S=500;
ll x[250005],y[250005];
double ex[250005];
int a[250005],b[250005];
bool cmp(int i,int j){return ex[i]<ex[j];}
int pos[250005],L[505],R[505];
vector<pair<int,int> > Query[250005];
ll ans[250005];
ll val[250005],mn[505];
ll getdis(int i,int j){return (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);}
void init(){
for(int i=1;i<=n;i++)val[i]=0x3f3f3f3f3f3f3f3f;
for(int i=1;i<=pos[n];i++)mn[i]=0x3f3f3f3f3f3f3f3f;
}
void add(int x,ll y){
val[x]=min(val[x],y);
mn[pos[x]]=min(mn[pos[x]],y);
}
ll ask(int l){
ll res=0x3f3f3f3f3f3f3f3f;
for(int i=pos[l]+1;i<=pos[n];i++)res=min(res,mn[i]);
for(int i=l;i<=R[pos[l]];i++)res=min(res,val[i]);
return res;
}
int main(){
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
// puts("OK");
n=read(),q=read();B=sqrt(n);
double cs=cos(114514),sn=sin(114514);
for(int i=1;i<=n;i++)x[i]=read(),y[i]=read(),ex[i]=x[i]*cs-y[i]*sn;
for(int i=1;i<=n;i++)a[i]=i;
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++)b[a[i]]=i;
for(int i=1;i<=n;i++){
pos[i]=(i-1)/B+1;
if(!L[pos[i]])L[pos[i]]=i;
R[pos[i]]=i;
}
for(int i=1;i<=q;i++){
int l=read(),r=read();
Query[r].push_back(make_pair(l,i));
}
init();
for(int i=1;i<=n;i++){
int lim=min(n,b[i]+S);
for(int j=max(1,b[i]-S);j<=lim;j++)if(a[j]<i)add(a[j],getdis(a[j],i));
for(int j=max(1,i-S);j<i;j++)add(j,getdis(j,i));
for(auto p:Query[i])ans[p.second]=ask(p.first);
}
for(int i=1;i<=q;i++)printf("%lld\n",ans[i]);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 19908kb
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: 2ms
memory: 20092kb
input:
2 1 1 1 1 1 1 2
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 0ms
memory: 19976kb
input:
2 1 1 100000000 100000000 1 1 2
output:
19999999600000002
result:
ok 1 number(s): "19999999600000002"
Test #4:
score: 0
Accepted
time: 109ms
memory: 23836kb
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: 115ms
memory: 23912kb
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: 0
Accepted
time: 120ms
memory: 23840kb
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:
ok 250000 numbers
Test #7:
score: 0
Accepted
time: 123ms
memory: 23912kb
input:
20000 250000 193144 901630 894860 3728 802840 155641 625273 792794 433205 942335 223506 874548 425235 550629 341169 950916 49296 305542 709463 512381 9742 994078 106664 845553 38691 373010 184728 331946 344567 438182 854583 291040 94405 555036 56330 494420 928479 123077 796593 798314 300374 490072 2...
output:
3576676 1219565 93925 2336788 8872 68 137 842657 137 8560936 13914025 28521 88362 8872 8872 52996 12869 86297 68 8137625 93925 12869 86297 8872 8872 8872 47888 8872 12869 107860 12869 59536 59536 425540 12869 59536 8872 93925 117225 137 137 52996 68 52996 137 8872 68 12869 137 68 86297 1514 159700 6...
result:
ok 250000 numbers
Test #8:
score: 0
Accepted
time: 125ms
memory: 23808kb
input:
20000 250000 65468917 46637638 46041830 58072288 95596278 49154795 57837493 40861050 21328886 69542502 7729300 7126264 2317013 48080367 75669670 20165373 93996778 88884044 8523082 62327896 123901 11925128 71901024 73104267 94991893 98591670 53591520 11543761 76785613 86286274 64694742 89591932 75687...
output:
185588005 3282196826 141969393 25769005 141969393 185588005 576346153849 141969393 141969393 185588005 141969393 141969393 141969393 141969393 135584833 141969393 141969393 485404589 1182793 1182793 35224007589 135584833 185588005 931246420 185588005 25769005 375240717 141969393 2245310308 239709665...
result:
ok 250000 numbers
Test #9:
score: 0
Accepted
time: 1002ms
memory: 27220kb
input:
250000 250000 1 2 1 1 3 2 3 3 1 2 3 2 1 2 1 3 3 1 2 1 1 3 2 3 3 3 1 3 3 1 3 1 1 3 2 1 1 2 1 1 1 2 2 2 1 2 1 2 1 3 3 3 1 1 3 2 1 2 2 2 1 1 2 3 3 2 2 1 3 3 2 1 2 3 3 1 2 3 3 2 2 1 1 1 3 2 1 2 1 3 3 1 2 3 2 1 1 2 1 1 1 2 3 3 1 2 2 2 3 1 3 1 3 1 1 2 2 2 1 1 3 3 1 3 1 3 1 2 1 2 3 1 3 2 1 2 2 2 1 2 1 1 2 ...
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 #10:
score: -100
Wrong Answer
time: 1434ms
memory: 27132kb
input:
250000 250000 65 333 64 141 52 164 104 499 329 292 187 279 178 394 92 488 223 487 457 262 355 475 466 223 450 293 397 22 390 379 257 389 339 162 228 267 446 78 116 3 28 400 63 319 255 491 459 301 340 321 183 340 469 6 288 268 383 446 456 13 478 383 109 79 142 317 132 219 168 347 30 398 59 453 192 33...
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 1 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 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer 97665th numbers differ - expected: '1', found: '2'