Submission #253187

#	Time	Username	Problem	Language	Result	Execution time	Memory
253187		vioalbert	Wish (LMIO19_noras)	C++14	100 / 100	176 ms	15076 KiB

noras

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

const ll N = 2e5+5, INF = 1e18, SQRINF = 1e9;
ll n, R;
ll a[N], b[N], c[N], d[N];
vector<pair<ll, ll>> events;

void read() {
	cin >> n >> R;
	for(int i = 0; i < n; i++)
		cin >> a[i] >> b[i] >> c[i] >> d[i];
}

ll val(ll a, ll b, ll c, ll d, ll t) {
	ll r1 = a + (c - a) * t;
	ll r2 = b + (d - b) * t;
	return min(INF, ((r1>=SQRINF || r1<=-SQRINF)?INF:(r1*r1)) + ((r2>=SQRINF || r2<=-SQRINF)?INF:(r2*r2)));
}

void solve() {
	for(int i = 0; i < n; i++) {
		pair<ll, ll> ans = {INF, INF};
		ll x1, x2, l, r, xx;
		ll nom = a[i] * (a[i] - c[i]) + b[i] * (b[i] - d[i]);
		ll den = (a[i] - c[i]) * (a[i] - c[i]) + (b[i] - d[i]) * (b[i] - d[i]);
		if(nom % den == 0) {
			x1 = x2 = nom / den;
		} else {
			x1 = nom / den;
			x2 = x1 + 1;
		}
		x1 = max(0ll, x1), x2 = max(0ll, x2);
		if(val(a[i], b[i], c[i], d[i], x2) < val(a[i], b[i], c[i], d[i], x1)) x1 = x2;
		if(val(a[i], b[i], c[i], d[i], x1) > R*R) continue;

		xx = INF;
		l = 0, r = x1;
		while(l <= r) {
			ll mid = (l+r)/2;
			if(val(a[i], b[i], c[i], d[i], mid) <= R*R)
				xx = mid, r = mid-1;
			else
				l = mid+1;
		}
		ans.first = xx;

		xx = INF;
		l = x1, r = 1e9;
		while(l <= r) {
			ll mid = (l+r)/2;
			if(val(a[i], b[i], c[i], d[i], mid) <= R*R)
				xx = mid, l = mid+1;
			else
				r = mid-1;
		}
		ans.second = xx;

		if(ans.first == INF || ans.second == INF) continue;
		events.push_back({ans.first, 1});
		events.push_back({ans.second+1, -1});
	}
	sort(events.begin(), events.end());
	ll ans = 0, cur = 0, prv = 0;
	for(auto e : events) {
		cur += e.second;
		ans = max(ans, cur);
		prv = e.first;
	}
	cout << ans << '\n';
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	read();
	solve();
	return 0;
}

Compilation message (stderr)

noras.cpp: In function 'void solve()':
noras.cpp:65:23: warning: variable 'prv' set but not used [-Wunused-but-set-variable]
  ll ans = 0, cur = 0, prv = 0;
                       ^~~

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