oj.uz

Submission #375755

# Submission time Handle Problem Language Result Execution time Memory
375755 2021-03-10T00:13:20 Z mode149256 Wish (LMIO19_noras) C++17
0 / 100
 1 ms 492 KB 
/*input
10 10
8 -1 23 -1
-17 4 -33 4
-13 -4 -26 -4
-14 1 -33 1
8 7 19 7
-18 -9 -36 -9
20 -5 35 -5
-20 1 -37 1
9 1 25 1
21 -5 35 -5


*/
#include <bits/stdc++.h>

using namespace std;

#define F first
#define S second

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

const int MAX_N = 200005;
const ll INF = 2e9;

struct Star
{
	pll pos;
	pll dir;
};

int N;
ll R;
Star Stars[MAX_N];

pll getNth(pll pos, pll dir, ll n)
{
	if (n < 0) return {INF, INF};

	// printf("ret = %lld %lld\n", pos.F + n * dir.F, pos.S + n * dir.S);
	// printf("new = %lld %lld\n", max(-INF / 2, min(INF / 2, pos.F + n * dir.F)), max(-INF / 2, min(INF / 2, pos.S + n * dir.S)));
	// return make_pair(pos.F + n * dir.F, pos.S + n * dir.S);

	return make_pair(max(-INF, min(INF, pos.F + n * dir.F)), max(-INF, min(INF, pos.S + n * dir.S)));
}

ll getINF(pll dir)
{
	return INF / max(abs(dir.F), abs(dir.S));
}

ll closest(Star star)
{
	ll lo = 0, hi = getINF(star.dir);
	while (lo < hi)
	{
		ll mid = (lo + hi) / 2;
		pll pos1 = getNth(star.pos, star.dir, mid);
		pll pos2 = getNth(star.pos, star.dir, mid + 1);
		ll d1 = pos1.F * pos1.F + pos1.S * pos1.S;
		ll d2 = pos2.F * pos2.F + pos2.S * pos2.S;

		if (d1 == d2)
		{
			return mid;
		}
		else if (d1 < d2)
		{
			hi = mid;
		}
		else
		{
			lo = mid + 1;
		}
	}

	return lo;
}

int main()
{
	scanf("%d%lld", &N, &R);

	for (int i = 0; i < N; i++)
	{
		ll a, b, c, d;
		scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
		Stars[i] = {{a, b}, {c - a, d - b}};
	}

	vector<pll> Intervals;

	for (int i = 0; i < N; i++)
	{
		ll close = closest(Stars[i]);
		pll closestPos = getNth(Stars[i].pos, Stars[i].dir, close);

		if (closestPos.F * closestPos.F + closestPos.S * closestPos.S > R * R)
			continue;

		ll l = close, r = close;

		ll did = getINF(Stars[i].dir);

		for (ll step = did; step > 0; step /= 2)
		{
			pll pos = getNth(Stars[i].pos, Stars[i].dir, l - step);
			if (pos.F * pos.F + pos.S * pos.S <= R * R)
			{
				l -= step;
			}
		}

		for (ll step = did; step > 0; step /= 2)
		{
			pll pos = getNth(Stars[i].pos, Stars[i].dir, r + step);
			if (pos.F * pos.F + pos.S * pos.S <= R * R)
			{
				r += step;
			}
		}

		//cerr << l << " " << r << endl;

		Intervals.push_back({l, 1});
		Intervals.push_back({r + 1, -1});
	}

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

	ll best = 0;
	ll curr = 0;

	for (pll p : Intervals)
	{
		curr += p.S;
		best = max(best, curr);
	}

	printf("%lld", best);

	return 0;
}

Compilation message

noras.cpp: In function 'int main()':
noras.cpp:85:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   85 |  scanf("%d%lld", &N, &R);
      |  ~~~~~^~~~~~~~~~~~~~~~~~
noras.cpp:90:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   90 |   scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 1 ms 492 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 1 ms 492 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 1 ms 492 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 1 ms 492 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 1 ms 492 KB Output isn't correct
4 Halted 0 ms 0 KB -