QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#131876#5136. Lowest LatencyPetroTarnavskyi#TL 0ms0kbC++173.1kb2023-07-28 18:10:212023-07-28 18:10:22

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-28 18:10:22]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2023-07-28 18:10:21]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define MP make_pair
#define PB push_back
#define F first
#define S second
#define FILL(a, b) memset(a, b, sizeof(a))

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;

typedef long double db;

const int N = 1 << 17;
const int INF = 1e9;
int x[N][3];

db dist(int i, int j){
	db sum = 0;
	FOR(t, 0, 3){
		db d = x[i][t] - x[j][t];
		sum += d * d;
	}
	return sqrt(sum);
}

db bin_d;
bool OK(int i, int j){
	return dist(i, j) < bin_d;
}

struct Tree{
	set<PII> ys[2 * N];
	
	
	void add(int v, int tl, int tr, int l, int r, int i){
		if(l > r)
			return;
		if(tl == l && tr == r){
			ys[v].insert(MP(x[i][1], i));
			return;
		}
		int tm = (tl + tr) / 2;
		add(2 * v, tl, tm, l, min(r, tm), i);
		add(2 * v + 1, tm + 1, tr, max(tm + 1, l), r, i);
	}
	void rem(int v, int tl, int tr, int l, int r, int i){
		if(l > r)
			return;
		if(tl == l && tr == r){
			ys[v].erase(MP(x[i][1], i));
			return;
		}
		int tm = (tl + tr) / 2;
		rem(2 * v, tl, tm, l, min(r, tm), i);
		rem(2 * v + 1, tm + 1, tr, max(tm + 1, l), r, i);
	}
	
	
	
	bool check(int v, int i, int d){
		auto it = ys[v].lower_bound(MP(x[i][1] - d, -1));
		
		while(it != ys[v].end()){
			if(it->F > x[i][1] + d)
				break;
			
			if(it->S != i && OK(i, it->S))
				return 1;
			it++;
		}
		return 0;
	}
	bool check(int v, int tl, int tr, int pos, int i, int d){
		if(check(v, i, d))
			return 1;
	
		if(tl == tr)
			return 0;
		
		int tm = (tl + tr) / 2;
		if(pos <= tm)
			return check(2 * v, tl, tm, pos, i, d);
		return check(2 * v + 1, tm + 1, tr, pos, i, d);
	}
}T;


bool check(int n, db m){
	bin_d = m;
	
	int d = int(m) + 1;
	
	vector<PII> events(3 * n);
	FOR(i, 0, n){
		events[3 * i] = MP(x[i][2] - d, i + 1);
		events[3 * i + 1] = MP(x[i][2] + d + 1, -(i + 1));
		events[3 * i + 2] = MP(x[i][2], INF + i);
	}
	sort(ALL(events));
	
	VI xs(n);
	FOR(i, 0, n)
		xs[i] = x[i][0];
	sort(ALL(xs));
	
	
	set<int> idx;
	
	FOR(it, 0, 3 * n){
		int id = events[it].S;
		if(id >= INF){
			//query
			id -= INF;

			
			
			int pos = lower_bound(ALL(xs), x[id][0]) - xs.begin();	
			if(T.check(1, 0, n - 1, pos, id, d))
				return 1;
			
			continue;
		}
		
		int t = (id > 0);
		id = abs(id) - 1;
		
		int lx = lower_bound(ALL(xs), x[id][0] - d) - xs.begin();
		int rx = upper_bound(ALL(xs), x[id][0] + d) - xs.begin() - 1;
		
		
		if(t){
			T.add(1, 0, n - 1, lx, rx, id);
			idx.insert(id);
		}
		else{
			T.rem(1, 0, n - 1, lx, rx, id);
			idx.erase(id);
		}
	}
	return 0;
}



int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	FOR(i, 0, n)
		FOR(t, 0, 3)
			cin >> x[i][t];
	
	
	
	
	db l = 0, r = 2e9;
	FOR(t, 0, 47){
		db m = bin_d = (l + r) / 2;
		
		if(check(n, m))
			r = m;
		else
			l = m;
	}
	cout << fixed << setprecision(10) << r << endl;
	
	
	
	return 0;
}

詳細信息

Test #1:

score: 0
Time Limit Exceeded

input:

100000
332143901 284102352 570195534
434050088 127258259 405899431
771419785 591983836 993571739
840022894 817836335 522977053
838660826 594804134 22555488
479844553 644693351 113265148
856575556 931653385 248482595
167010514 77957036 379182090
563518287 572234979 55605040
653604447 286132667 814469...

output:


result: