Submission #716175

#	Time	Username	Problem	Language	Result	Execution time	Memory
716175		amunduzbaev	Wish (LMIO19_noras)	C++17	100 / 100	337 ms	29480 KiB

noras

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef long long ll;
#define int __int128
 
const int N = 2e5 + 5;
const int MX = 1e9;
ll a[N], b[N], c[N], d[N];
int l_[N], r_[N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	ll n, R; cin >> n >> R;
	for(int i=0;i<n;i++){
		cin >> a[i] >> b[i] >> c[i] >> d[i];
		c[i] -= a[i], d[i] -= b[i];
	}
	auto sq = [&](int x) -> __int128{
		return x * x;
	};
	
	for(int i=0;i<n;i++){
		auto check = [&](int t) -> __int128{
			int x = a[i] + c[i] * t, y = b[i] + d[i] * t;
			return sq(x) + sq(y);
		};
		
		int l = 0, r = MX;
		//~ if(c[i]) r = abs(MX / c[i]);
		//~ if(d[i]) r = min(r, abs(MX / d[i]));
		int mx = r;
		while(l + 2 < r){
			int m = (l + r) >> 1;
			if(check(m) <= check(m + 1)){
				r = m + 1;
			} else {
				l = m;
			}
		}
		l_[i] = r_[i] = -1;
		int T = l;
		if(check(T) > check(l + 1)) T = l + 1;
		if(check(T) > check(r)) T = r;
		
		if(check(T) > sq(R)) continue;
		
		l = 0, r = T;
		while(l < r){
			int m = (l + r) >> 1;
			if(check(m) <= sq(R)) r = m;
			else l = m + 1;
		}
		
		l_[i] = l;
		l = T, r = mx;
		while(l < r){
			int m = (l + r) >> 1;
			if(check(m) > sq(R)) r = m;
			else l = m + 1;
		}
		r_[i] = l;
	}
	
	vector<ar<int, 2>> tot;
	for(int i=0;i<n;i++){
		tot.push_back({l_[i], 1});
		tot.push_back({r_[i], -1});
	}
	
	sort(tot.begin(), tot.end());
	ll res = 0, cur = 0;
	for(auto [a, b] : tot){
		cur += b;
		res = max(res, cur);
	}
	
	cout<<res<<"\n";
}

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