Submission #253181

#	Time	Username	Problem	Language	Result	Execution time	Memory
253181		Berted	Wish (LMIO19_noras)	C++14	100 / 100	166 ms	5344 KiB

noras

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#define ll long long
#define EL __int128_t
#define pii pair<ll, ll>
#define fst first
#define snd second
using namespace std;

const ll INF = 2e18;

inline ll fsqrt(EL val)
{
	ll L = 1, R = INF;
	while (L < R)
	{
		ll M = L + R >> 1;
		EL t = M; t = t * t;
		if (t <= val) {L = M + 1;}
		else {R = M;}
	}
	return L - 1;
}

ll flr(ll a, ll b)
{
	if (a < 0) return (a - b + 1) / b;
	else return a / b;
}

ll cil(ll a, ll b)
{
	if (a < 0) return a / b;
	else return (a + b - 1) / b;
}

inline string dts(EL x)
{
	string lol = ""; bool f = 0;
	if (x < 0) {f = 1; x = -x;}
	while (x)
	{
		lol = (char)(x % 10 + '0') + lol;
		x /= 10;
	}
	if (lol.size() == 0) lol.push_back('0');
	else if (f) lol = '-' + lol;
	return lol;
}

vector<pii> ivl;
priority_queue<int, vector<int>, greater<int>> pq;

int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n; ll r;
	cin >> n >> r;
	for (int i = 0; i < n; i++)
	{
		ll x0, y0, vx, vy;
		cin >> x0 >> y0 >> vx >> vy;
		vx -= x0; vy -= y0;
		EL a = vx * vx + vy * vy, b = 2 * (vx * x0 + vy * y0), c = x0 * x0 + y0 * y0 - r * r;
		EL D = b * b - 4 * a * c;

		// cout << dts(a) << " " << dts(b) << " " << dts(c) << " " << dts(D) << "\n";
		ll L = 1, R = 0;
		if (D == 0) {L = cil(-b, 2 * a); R = flr(-b, 2 * a);}
		else if (D > 0)
		{
			ll res = fsqrt(D);
			L = cil(-b - res, 2 * a); R = flr(-b + res, 2 * a);
		}
		L = max(0LL, L);
		if (L <= R) {ivl.push_back({L, R});}
	} 
	sort(ivl.begin(), ivl.end());
	int res = 0;
	for (int i = 0; i < ivl.size(); i++)
	{
		while (pq.size() && pq.top() < ivl[i].fst) {pq.pop();}
		pq.push(ivl[i].snd);
		res = max(res, (int)pq.size());
	}
	cout << res << "\n";
	return 0;
}

Compilation message (stderr)

noras.cpp: In function 'long long int fsqrt(__int128)':
noras.cpp:19:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   ll M = L + R >> 1;
          ~~^~~
noras.cpp: In function 'int main()':
noras.cpp:82:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < ivl.size(); i++)
                  ~~^~~~~~~~~~~~

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