Submission #253285

#	Time	Username	Problem	Language	Result	Execution time	Memory
253285		DystoriaX	Wish (LMIO19_noras)	C++14	93 / 100	470 ms	21268 KiB

noras

#include <bits/stdc++.h>

using namespace std;

typedef pair<__int128, int> pii;

int n, r;
int a[200010], b[200010], dx[200010], dy[200010];
int pref[200010];

vector<pii> v;

__int128 sq(__int128 x){
	return x * x;
}

__int128 sqDist(__int128 dx, __int128 dy){
	return sq(dx) + sq(dy);
}

bool check(__int128 dx, __int128 dy){
	return sqDist(dx, dy) <= sq(r);
}

bool check(__int128 d){
	return d <= sq(r);
}

__int128 TernarySearch(int a, int b, int dx, int dy){
	__int128 l, r, tp, ret;

	l = ceil((1e8 - a) / abs(dx)), r = ceil((1e8 - b) / abs(dy));

	r = max(l, r);
	l = 0;
	if(r < 0) return -1;

	tp = 4e18; ret = -1;

	while(l <= r){
		__int128 m1, m2, v1, v2;

		m1 = l + (r - l) / 3;
		m2 = r - (r - l) / 3;

		v1 = sqDist(a + 1LL * m1 * dx, b + 1LL * m1 * dy);
		v2 = sqDist(a + 1LL * m2 * dx, b + 1LL * m2 * dy);

		if(v1 > v2){
			l = m1 + 1;

			if(tp > v2){
				ret = m2;
				tp = v2;
			}
		} else {
			r = m2 - 1;

			if(tp > v1){
				ret = m1;
				tp = v1;
			}
		}
	}

	if(check(tp)) return ret;
	else return -1;
}

__int128 SearchLeft(int a, int b, int dx, int dy, __int128 pvt){
	__int128 l, r;

	l = 0;
	r = pvt;

	while(l <= r){
		__int128 m = (l + r) >> 1;

		if(check(a + 1LL * m * dx, b + 1LL * m * dy)) r = m - 1;
		else l = m + 1;
	}

	return l;
}

__int128 SearchRight(int a, int b, int dx, int dy, __int128 pvt){
	__int128 l, r;
	l = ceil((1e8 - a) / abs(dx)), r = ceil((1e8 - b) / abs(dy));

	r = max(l, r);

	l = pvt;

	while(l <= r){
		__int128 m = (l + r) >> 1;

		if(check(a + 1LL * m * dx, b + 1LL * m * dy)) l = m + 1;
		else r = m - 1;
	}

	return r;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	cin >> n >> r;

	for(int i = 1; i <= n; i++){
		cin >> a[i] >> b[i] >> dx[i] >> dy[i];
		
		dx[i] -= a[i];
		dy[i] -= b[i];

		long long mn, mx, pvt;

		pvt = TernarySearch(a[i], b[i], dx[i], dy[i]);

		// cerr << i << ":\n";
		// cerr << pvt << "\n";

		if(pvt == -1) continue;

		mn = SearchLeft(a[i], b[i], dx[i], dy[i], pvt);
		mx = SearchRight(a[i], b[i], dx[i], dy[i], pvt);

		if(mn > mx) swap(mn, mx);

		// cerr << mn << " " << mx << "\n";


		if(mx >= 0 && mn <= mx){
			// cerr << mn << " " << mx << "\n";
			assert(check(a[i] + 1LL * mn * dx[i], b[i] + 1LL * mn * dy[i]));
			assert(check(a[i] + 1LL * mx * dx[i], b[i] + 1LL * mx * dy[i]));
			v.emplace_back(max(0LL, mn), 1);
			v.emplace_back(mx + 1, -1);
		}
		// for(int k = 0; k <= 20000; k++){
		// 	if(sq(a[i] + 1LL * k * dx[i]) + sq(b[i] + 1LL * k * dy[i]) <= sq(r)) pref[k]++;
		// }
	}

	int ans = 0, cnt = 0;

	sort(v.begin(), v.end());

	for(int i = 0; i < (int) v.size(); i++){
		int j = i;

		while(j < (int) v.size() && v[i].first == v[j].first){
			cnt += v[j++].second;
		}

		ans = max(ans, cnt);
		i = j - 1;
	}

	cout << ans << "\n";
	
	return 0;
}

• Subtask 1: 23 / 23
• Subtask 2: 23 / 23
• Subtask 3: 15 / 15
• Subtask 4: 32 / 32
• Subtask 5: 0 / 7