Submission #199924

#	Time	Username	Problem	Language	Result	Execution time	Memory
199924		SamAnd	Wish (LMIO19_noras)	C++17	100 / 100	155 ms	18224 KiB

noras

#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
struct ban
{
    long long x;
    int z;
    ban(){}
    ban(long long x, int z)
    {
        this->x = x;
        this->z = z;
    }
};
bool operator<(const ban& a, const ban& b)
{
    if (a.x < b.x)
        return true;
    if (a.x > b.x)
        return false;
    return a.z < b.z;
}

int n;
long long R;
long long a[N], b[N], c[N], d[N];

long long l[N], r[N];

int main()
{
    //freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin >> n >> R;
    for (int i = 1; i <= n; ++i)
        r[i] = -1;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        c[i] -= a[i];
        d[i] -= b[i];
        long double aa = c[i] * c[i] + d[i] * d[i];
        long double bb = 2 * a[i] * c[i] + 2 * b[i] * d[i];
        long double cc = a[i] * a[i] + b[i] * b[i] - R * R;
        long double D = bb * bb - 4 * aa * cc;
        D += 0.1;
        if (D < 0)
        {
            continue;
        }
        long double ll = (-sqrt(D) - bb) / (2 * aa);
        long double rr = (sqrt(D) - bb) / (2 * aa);
        for (long long k = ll - 5; k <= ll + 5; ++k)
        {
            if ((a[i] + c[i] * k) * (a[i] + c[i] * k) + (b[i] + d[i] * k) * (b[i] + d[i] * k) <= R * R)
            {
                l[i] = k;
                break;
            }
        }
        for (long long k = rr + 5; k >= rr - 5; --k)
        {
            if ((a[i] + c[i] * k) * (a[i] + c[i] * k) + (b[i] + d[i] * k) * (b[i] + d[i] * k) <= R * R)
            {
                r[i] = k;
                break;
            }
        }
        l[i] = max(l[i], 0LL);
        if (r[i] < l[i])
            r[i] = l[i] - 1;
    }
    vector<ban> v;
    for (int i = 1; i <= n; ++i)
    {
        v.push_back(ban(l[i], 1));
        v.push_back(ban(r[i] + 1, -1));
    }
    sort(v.begin(), v.end());
    int ans = 0;
    int yans = 0;
    for (int i = 0; i < v.size(); ++i)
    {
        yans += v[i].z;
        ans = max(ans, yans);
    }
    cout << ans << endl;
    return 0;
}

Compilation message (stderr)

noras.cpp: In function 'int main()':
noras.cpp:82:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v.size(); ++i)
                     ~~^~~~~~~~~~

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