Submission #716121

#	Time	Username	Problem	Language	Result	Execution time	Memory
716121		tengiz05	Wish (LMIO19_noras)	C++17	100 / 100	209 ms	12424 KiB

noras

#include <bits/stdc++.h>

using i64 = long long;

struct Vector {
    i64 x, y;
    Vector(i64 x = 0, i64 y = 0) : x(x), y(y) {}
    Vector operator-(Vector b) {
        return Vector(x - b.x, y - b.y);
    }
    Vector operator+(Vector b) {
        return Vector(x + b.x, y + b.y);
    }
    Vector operator*(i64 k) {
        return Vector(x * k, y * k);
    }
    __int128 length() {
        return __int128(x) * x + __int128(y) * y;
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    i64 Rin;
    std::cin >> n >> Rin;
    __int128 R = __int128(Rin) * Rin;
    
    std::vector<Vector> a(n), b(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i].x >> a[i].y >> b[i].x >> b[i].y;
    }
    
    std::vector<std::pair<int, int>> v;
    for (int i = 0; i < n; i++) {
        Vector cur = a[i];
        Vector delta = b[i] - a[i];
        int lo = 0, hi = 1E9;
        while (lo + 3 < hi) {
            int m = (lo + hi + 1) / 2;
            if ((cur + delta * m).length() > (cur + delta * (m + 1)).length()) {
                lo = m;
            } else {
                hi = m - 1;
            }
        }
        int p = std::max(0, lo - 4);
        while (p < lo + 4 && (cur + delta * p).length() > R) p++;
        if ((cur + delta * p).length() > R) continue;
        cur = cur + delta * p;
        lo = 0, hi = 1E9;
        while (lo < hi) {
            int m = (lo + hi + 1) / 2;
            if ((cur - delta * m).length() <= R) {
                lo = m;
            } else {
                hi = m - 1;
            }
        }
        int l = std::max(0, p - lo);
        lo = 0, hi = 1E9;
        while (lo < hi) {
            int m = (lo + hi + 1) / 2;
            if ((cur + delta * m).length() <= R) {
                lo = m;
            } else {
                hi = m - 1;
            }
        }
        int r = p + lo;
        v.push_back({l, r});
    }
    
    std::vector<std::pair<int, int>> events;
    for (auto [l, r] : v) {
        events.emplace_back(l, 1);
        events.emplace_back(r + 1, -1);
    }
    std::sort(events.begin(), events.end());
    int k = events.size();
    int cnt = 0;
    int ans = 0;
    for (int i = 0; i < k; ) {
        int j = i;
        while (j < k && events[i].first == events[j].first)
            j++;
        while (i < j) {
            cnt += events[i].second;
            i++;
        }
        ans = std::max(ans, cnt);
    }
    
    std::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