oj.uz

Submission #375749

# Submission time Handle Problem Language Result Execution time Memory
375749 2021-03-10T00:00:42 Z mode149256 Wish (LMIO19_noras) C++17
0 / 100
 1 ms 364 KB 
/*input
3 2
-5 0 -4 0
3 0 2 0
10 0 9 0

2 1
-3 -2 -1 -1
-2 2 -1 1

2 2
3 0 5 0
-2 1 2 1
*/
#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};

	return make_pair(pos.F + n * dir.F, 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;

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

		for (ll step = close; step > 0; step /= 2)
		{
			pll pos = getNth(Stars[i].pos, Stars[i].dir, r + step);
			while (pos.F * pos.F + pos.S * pos.S <= R * R)
			{
				r += step;
				pos = getNth(Stars[i].pos, Stars[i].dir, 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;

	int j = 0;
	while (j < (int)Intervals.size()) {
		ll dabar = Intervals[j].F;
		while (j < (int)Intervals.size() and Intervals[j].F == dabar) {
			curr += Intervals[j].S;
			j++;
		}
		best = max(best, curr);
	}

	printf("%lld", best);

	return 0;
}

Compilation message

noras.cpp: In function 'int main()':
noras.cpp:80:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   80 |  scanf("%d%lld", &N, &R);
      |  ~~~~~^~~~~~~~~~~~~~~~~~
noras.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   85 |   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 0 ms 364 KB Output is correct
3 Incorrect 1 ms 364 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 0 ms 364 KB Output is correct
3 Incorrect 1 ms 364 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 0 ms 364 KB Output is correct
3 Incorrect 1 ms 364 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 0 ms 364 KB Output is correct
3 Incorrect 1 ms 364 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 0 ms 364 KB Output is correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -