Submission #375859

#	Time	Username	Problem	Language	Result	Execution time	Memory
375859		_martynas	Wish (LMIO19_noras)	C++11	100 / 100	222 ms	17920 KiB

noras

#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)
{
    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(l - step >= 0 && 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 = getINF(Stars[i].dir); 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);
            }
        }

        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 (stderr)

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

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