Submission #708378

#	Time	Username	Problem	Language	Result	Execution time	Memory
708378		tamyte	Wish (LMIO19_noras)	C++14	100 / 100	155 ms	17216 KiB

noras

#include <bits/stdc++.h>

using namespace std;
#define sz(x) (int)(x).size()
void setIO(string name = "") {
    cin.tie(0)->sync_with_stdio(0); // see /general/fast-io
    if (sz(name)) {
        freopen((name + ".in").c_str(), "r", stdin); // see /general/input-output
        freopen((name + ".out").c_str(), "w", stdout);
    }
}

/*----------------------------------*/

typedef long long ll;


struct star
{
    long long x, y;
    long long dx, dy;
} stars[(int)2e5 + 1];

bool find_roots(int i, long double &root1, long double &root2, long long r) {
    long long a, b, c;
    a = stars[i].dx * stars[i].dx + stars[i].dy * stars[i].dy;
    b = 2 * stars[i].dx * stars[i].x + 2 * stars[i].dy * stars[i].y;
    c = stars[i].x * stars[i].x + stars[i].y * stars[i].y - r * r;
    __int128 d = (__int128)b * b - (__int128) 4 * a * c;
    if (d < 0) return false;
    long double D = sqrt((long double)d);
    root1 = (-b - D) / (2.L * a);
    root2 = (-b + D) / (2.L * a);
    return true;
}

bool cmp(const pair<long long, int>& a, const pair<long long, int>& b) {
    if (a.first != b.first) return a.first < b.first;
    return a.second > b.second;
}

int main() {
    setIO("");
    int n;
    ll r;
    cin >> n >> r;
    vector<pair<long long, int>> interval;
    for (int i = 0; i < n; ++i) {
        cin >> stars[i].x >> stars[i].y >> stars[i].dx >> stars[i].dy;
        stars[i].dx -= stars[i].x;
        stars[i].dy -= stars[i].y;
        long double root1, root2;
        if (!find_roots(i, root1, root2, r)) continue;
        long long start = max(0.L, ceil(root1)), finish = floor(root2);
        if (start > finish) continue;   
        interval.push_back({start, 1});
        interval.push_back({finish, -1});
    }
    sort(interval.begin(), interval.end(), cmp);
    int mx = 0, curr = 0;
    for (auto u : interval) {
        // cout << u.first << " " << u.second << "\n";
        curr += u.second;
        mx = max(mx, curr);
    }
    cout << mx;
}

Compilation message (stderr)

noras.cpp: In function 'void setIO(std::string)':
noras.cpp:8:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |         freopen((name + ".in").c_str(), "r", stdin); // see /general/input-output
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
noras.cpp:9:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |         freopen((name + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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