QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#122583#5463. Range Closest Pair of Points QueryCharlieVinnieWA 246ms194764kbC++141.7kb2023-07-10 19:34:202023-07-10 19:34:25

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-10 19:34:25]
  • 评测
  • 测评结果:WA
  • 用时:246ms
  • 内存:194764kb
  • [2023-07-10 19:34:20]
  • 提交

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(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: 23ms
memory: 189780kb

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: 19ms
memory: 191836kb

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: 191828kb

input:

2 1
1 100000000
100000000 1
1 2

output:

19999999600000002

result:

ok 1 number(s): "19999999600000002"

Test #4:

score: -100
Wrong Answer
time: 246ms
memory: 194764kb

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 38262nd numbers differ - expected: '0', found: '1'