oj.uz

답안 #716101

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
716101 2023-03-29T03:26:54 Z tengiz05 Wish (LMIO19_noras) C++17
0 / 100
 809 ms 464 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);
    }
    i64 length() {
        return x * x + y * y;
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    i64 R;
    std::cin >> n >> R;
    
    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 < 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;
            }
        }
        Vector orig = cur;
        cur = cur + delta * lo;
        if (cur.length() > R * R) {
            cur = cur + delta;
            lo++;
        }
        if (cur.length() > R * R) continue;
        int l = lo;
        while (l > 0 && (cur - delta).length() <= R * R) {
            cur = cur - delta;
            l--;
        }
        int r = l;
        while (r < 20000 && (cur + delta).length() <= R * 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;
}

Compilation message

noras.cpp: In function 'int main()':
noras.cpp:48:16: warning: variable 'orig' set but not used [-Wunused-but-set-variable]
   48 |         Vector orig = cur;
      |                ^~~~

Subtask #1
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 809 ms 464 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 809 ms 464 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 809 ms 464 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 809 ms 464 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 809 ms 464 KB Output isn't correct
4 Halted 0 ms 0 KB -