QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#122576 | #5463. Range Closest Pair of Points Query | CharlieVinnie | WA | 221ms | 195676kb | C++14 | 1.7kb | 2023-07-10 19:28:42 | 2023-07-10 19:31:38 |
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=N*30,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)); }
}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)<<31)+y; }
void update(int u,ll id,int i,bool flg){
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(flg&&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=1;(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: 32ms
memory: 191828kb
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: 24ms
memory: 191888kb
input:
2 1 1 1 1 1 1 2
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 16ms
memory: 189852kb
input:
2 1 1 100000000 100000000 1 1 2
output:
19999999600000002
result:
ok 1 number(s): "19999999600000002"
Test #4:
score: -100
Wrong Answer
time: 221ms
memory: 195676kb
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 935th numbers differ - expected: '0', found: '1'