oj.uz

Submission #375710

# Submission time Handle Problem Language Result Execution time Memory
375710 2021-03-09T19:36:48 Z _martynas Wish (LMIO19_noras) C++11
0 / 100
 2 ms 492 KB 
#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(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;

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

    printf("%lld", best);

    return 0;
}

/*
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
*/

Compilation message

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
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 2 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 492 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 2 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 492 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 2 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 492 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 2 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 492 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 2 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -