Submission #375607

#	Time	Username	Problem	Language	Result	Execution time	Memory
375607		mode149256	Wish (LMIO19_noras)	C++17	93 / 100	414 ms	15336 KiB

noras

/*input
2 1
-3 -2 -1 -1
-2 2 -1 1
*/
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second

using ll = long long;
using pl = pair<ll, ll>;

struct beam {
	pl prad;
	pl dxy; // {dx, dy}
};
int N, R;

ll dis(pl a, pl b) { // squared distance
	return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

// 0th second yra prad
pl getnth(ll n, beam b) {
	return {b.prad.x + n * b.dxy.x, b.prad.y + n * b.dxy.y};
}
vector<beam> sk;

ll getINF(beam b) {
	return ((ll)200000007) / max(abs(b.dxy.x), abs(b.dxy.y));
}
pl og = {0, 0};

ll closest(beam b){
	ll l = 0;
	ll h = getINF(b);
	// printf("%lld %lld, %lld %lld, h = %lld\n", b.prad.x, b.prad.y, b.dxy.x, b.dxy.y, h);
	ll m;
	while (h - l > 6) {
		m = (l + h) / 2;
		pl n1 = getnth(m, b);
		pl n2 = getnth(m + 1, b);
		ll d1 = dis(n1, og);
		ll d2 = dis(n2, og);

		if (d1 == d2) {
			return m;
		} else if (d1 < d2) {
			h = m;
		} else {
			l = m;
		}
	}

	pl ret = getnth(l, b);
	ll n = l;
	ll c = dis(ret, og);
	for (ll i = l + 1; i <= h; ++i)
	{
		pl nl = getnth(i, b);
		ll nc = dis(nl, og);
		if (nc < c) {
			c = nc;
			ret = nl;
			n = i;
		}
	}
	return n;
}

ll getFirst(beam b, ll best) {
	ll l = 0;
	ll h = best;
	ll m;
	while (l < h) {
		m = (l + h) / 2;

		pl n1 = getnth(m, b);
		ll d1 = dis(n1, og);

		if (d1 <= R * R) {
			h = m;
		} else {
			l = m + 1;
		}
	}
	return l;
}

ll getLast(beam b, ll best) {
	ll l = best;
	ll h = getINF(b);
	ll m;
	while (l < h) {
		m = (l + h + 1) / 2;

		pl n1 = getnth(m, b);
		ll d1 = dis(n1, og);

		if (d1 <= R * R) {
			l = m;
		} else {
			h = m - 1;
		}
	}
	return l;
}

int main() {
	cin >> N >> R;
	sk.resize(N);
	for (int i = 0; i < N; ++i)
	{
		ll a, b, c, d;
		cin >> a >> b >> c >> d;
		sk[i] = beam{{a, b}, {c - a, d - b}};
	}

	vector<pair<ll, ll>> inter;

	for (auto b : sk) {
		ll best = closest(b);
		if (dis(getnth(best, b), og) > R * R) {
			continue;
		}

		ll pirm = getFirst(b, best);
		ll gal = getLast(b, best);

		inter.emplace_back(pirm, +1);
		inter.emplace_back(gal + 1, -1);
		//[pirm, gal]
	}

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

	ll ats = 0;
	ll curr = 0;

	int j = 0;
	while (j < (int)inter.size()) {
		ll dabar = inter[j].x;
		while (j < (int)inter.size() && inter[j].x == dabar) {
			curr += inter[j].y;
			j++;
		}

		ats = max(ats, curr);
	}
	cout << ats << '\n';
}

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