oj.uz

Submission #716104

# Submission time Handle Problem Language Result Execution time Memory
716104 2023-03-29T03:40:54 Z tengiz05 Wish (LMIO19_noras) C++17
0 / 100
 1 ms 212 KB 
#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 = 20000;
        while (lo < hi) {
            int m = (lo + hi + 1) / 2;
            if (cur.length() >= (delta * m).length() && cur.length() >= (cur + delta * m).length()) {
                lo = m;
            } else {
                hi = m - 1;
            }
        }
        cur = cur + delta * lo;
        if (cur.length() > R) {
            cur = cur + delta;
            lo++;
        }
        if (cur.length() > R) continue;
        int l = -1, r = -1;
        cur = a[i];
        delta = b[i] - a[i];
        for (int j = 0; j < 20005; j++) {
            if (cur.length() <= R * R) {
                if (l == -1) {
                    l = j;
                }
                r = j;
            }
            cur = cur + delta;
        }
        v.push_back({l, r});
        //~ int l = lo;
        //~ while (l > 0 && (cur - delta).length() <= R) {
            //~ cur = cur - delta;
            //~ l--;
        //~ }
        //~ int r = l;
        //~ while ((cur + delta).length() <= R) {
            //~ cur = cur + delta;
            //~ r++;
        //~ }
        //~ 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
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -