Submission #213067

#	Time	Username	Problem	Language	Result	Execution time	Memory
213067		qkxwsm	Wish (LMIO19_noras)	C++14	100 / 100	228 ms	10232 KiB

noras

#include <bits/stdc++.h>

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
    if (a > b) a = b;
}

template<class T, class U>
void ckmax(T &a, U b)
{
    if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)

typedef __int128_t ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
typedef pair<pll, pll> ppp;

const int MAXN = 200013;

int N;
ll R;
int ans;
map<ll, int> pref;

ll fdiv(ll a, ll b)
{
    return a / b - (a % b < 0);
}
ll cdiv(ll a, ll b)
{
    return a / b + (a % b > 0);
}
ll getsqrt(ll x)
{
    ll lo = 0, hi = 1e18;
    while(hi > lo)
    {
        ll mid = (hi + lo + 1) >> 1;
        if (mid * mid > x) hi = mid - 1;
        else lo = mid;
    }
    return lo;
}

int32_t main()
{
    cout << fixed << setprecision(12);
    cerr << fixed << setprecision(4);
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> N;
    long long rr; cin >> rr; R = rr;
    FOR(i, 0, N)
    {
        long long A, B, C, D;
        cin >> A >> B >> C >> D;
        ll a, b, c, d;
        a = A; b = B; c = C; d = D;
        c -= a; d -= b;
        ll r = c * c + d * d;
        ll s = 2 * b * d + 2 * a * c;
        ll t = a * a + b * b - R * R;
        // cerr << r << ' ' << s << ' ' << t << endl;
        if (s * s - 4 * r * t < 0) continue;
        ll sq = getsqrt(s * s - 4 * r * t);
        // cerr << -s-sq << ' ' << -s + sq << ' ' << 2 * r << endl;
        ll lo = cdiv(-s - sq, 2 * r), hi = fdiv(-s + sq, 2 * r);
        // cerr << lo << '@' << hi << endl;
        ckmax(lo, 0);
        if (lo > hi) continue;
        // cerr << lo << ',' << hi << endl;
        pref[lo]++; pref[hi + 1]--;
    }
    if (pref.empty())
    {
        cout << "0\n";
        return 0;
    }
    for (auto it = next(pref.begin()); it != pref.end(); it++)
    {
        it -> se += (prev(it)) -> se;
    }
    for (auto p : pref)
    {
        ckmax(ans, p.se);
    }
    cout << ans << '\n';
    return 0;
}

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