QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#122593 | #5463. Range Closest Pair of Points Query | CharlieVinnie | TL | 5806ms | 467764kb | C++14 | 1.9kb | 2023-07-10 19:42:03 | 2023-07-10 19:42:05 |
Judging History
answer
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rev(i,a,b) for(int i=a;i>=b;i--)
#define Fin(file) freopen(file,"r",stdin);
#define Fout(file) freopen(file,"w",stdout);
using namespace std;
const int N=2.5e5+5,M=1.5e7,V=1e8; using ll = long long;
class STree{;
int n,B; ll a[N],b[N];
public:
void init(int nn) { n=nn; B=sqrt(n)+1; For(i,0,n) a[i]=b[i]=1e18; }
void poke(int x,ll y) { a[x]=min(a[x],y); b[x/B]=min(b[x/B],y); }
//~ ll peek(int x) { return min(*min_element(a+x,a+min(n,x/B*B+B-1)+1),*min_element(b+x/B+1,b+n/B+1)); }
ll peek(int x) { ll res=1e18; For(i,x,min(n,x/B*B+B-1)) res=min(res,a[i]);; For(i,x/B+1,n/B) res=min(res,b[i]);; return res; }
}T;
int n,Q,X[N],Y[N],tot; vector<pair<int,int>> qry[N]; vector<int> lis[M]; ll ans[N];
//~ __gnu_pbds::gp_hash_table<ll,int> mp[30];
unordered_map<ll,int> mp[30];
ll dist(int i,int j) { return 1ll*(X[i]-X[j])*(X[i]-X[j])+1ll*(Y[i]-Y[j])*(Y[i]-Y[j]); }
ll ID(int x,int y) { return (ll(x)*10*V)+y; }
void update(int u,ll id,int i,bool flg){
if(!flg&&mp[i].find(id)==mp[i].end()) return;
if(mp[i].find(id)==mp[i].end()) mp[i][id]=++tot,assert(tot<M);
int o=mp[i][id]; vector<int> tmp; if(flg) tmp.push_back(u);
for(int v:lis[o]){
ll d=dist(u,v); T.poke(v,d); if(d>(i==0?0:1ll<<(i*2-2))) tmp.push_back(v);
}
lis[o].swap(tmp);
}
int main(){
ios::sync_with_stdio(0); cin.tie(0);
cin>>n>>Q; T.init(n); For(i,1,n) cin>>X[i]>>Y[i];
For(i,1,Q) { int l,r; cin>>l>>r; qry[r].emplace_back(l,i); ans[i]=1e18; }
For(r,1,n){
for(int i=0;(1<<i)<=V;i++){
int x=X[r]>>i,y=Y[r]>>i;
For(xx,x-1,x+1) For(yy,y-1,y+1){
if(xx<0||yy<0||xx>(V>>i)||yy>(V>>i)) continue;
update(r,ID(xx,yy),i,xx==x&&yy==y);
}
}
for(auto [l,id]:qry[r]) ans[id]=min(ans[id],T.peek(l));
}
For(i,1,Q) cout<<ans[i]<<'\n';
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 43ms
memory: 368012kb
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: 57ms
memory: 367996kb
input:
2 1 1 1 1 1 1 2
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 31ms
memory: 365912kb
input:
2 1 1 100000000 100000000 1 1 2
output:
19999999600000002
result:
ok 1 number(s): "19999999600000002"
Test #4:
score: 0
Accepted
time: 275ms
memory: 371676kb
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: 315ms
memory: 370720kb
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: 380ms
memory: 374672kb
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: 559ms
memory: 389180kb
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: 690ms
memory: 399864kb
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: 1239ms
memory: 373608kb
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: 0
Accepted
time: 3549ms
memory: 390060kb
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:
ok 250000 numbers
Test #11:
score: 0
Accepted
time: 5806ms
memory: 467764kb
input:
250000 250000 5939 214 4869 2285 3576 8124 1179 6365 863 9874 6034 7110 9688 5453 1631 1975 7330 8868 1035 8771 9222 9417 7858 1642 3145 4403 8553 6105 8162 2232 2192 4946 5925 8017 1235 5374 6897 5409 8507 8625 7239 4621 5581 4870 4979 1749 35 1282 9138 5489 1030 8851 4444 905 5808 4770 348 7535 16...
output:
1 4 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 25 1 0 0 0 1 0 0 0 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 2 0 2 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 1 0 0 0 0 0 0 0 0 0 0 0 1 0 4 0 0 0 1 21925 0 0 0 0 0 0 0 0 0 0 0 0...
result:
ok 250000 numbers
Test #12:
score: -100
Time Limit Exceeded
input:
250000 250000 7455187 75182576 14834779 53171998 80916167 45846874 44479602 88587946 22419247 21232863 45054521 14420458 26938419 38366452 40688894 64933635 58825078 27729802 43992064 49857990 80761962 17266078 67198634 69525730 78961694 90909521 86333066 79243240 75184949 63327693 20070526 51545836...