Submission #716153

#	Time	Username	Problem	Language	Result	Execution time	Memory
716153		amunduzbaev	Wish (LMIO19_noras)	C++17	0 / 100	69 ms	384 KiB

noras

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

#define ar array
typedef long long ll;
#define int ll

const int N = 2e5 + 5;
const int MX = 3e4;
int a[N], b[N], c[N], d[N];
int l_[N], r_[N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int 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;
		for(int i=T + 1;i<mx;i++){
			assert(check(i - 1) <= check(i));
		}
		for(int i=T-1;i>=0;i--){
			assert(check(i + 1) <= check(i));
		}
		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 + 1;
		if(l_[i]){
			assert(check(l_[i] - 1) > sq(R));
		}
		assert(check(r_[i] + 1) > sq(R));
	}
	
	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());
	int res = 0, cur = 0;
	for(auto [a, b] : tot){
		cur += b;
		res = max(res, cur);
	}
	
	cout<<res<<"\n";
}

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