Submission #894987

#TimeUsernameProblemLanguageResultExecution timeMemory
894987d4xnWish (LMIO19_noras)C++17
0 / 100
1 ms6740 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 1e6+6; int n, R, a[N], b[N], c[N], d[N]; map<int, int> f; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> R; for (int i = 0; i < n; i++) { cin >> a[i] >> b[i] >> c[i] >> d[i]; int x = c[i]-a[i]; int y = d[i]-b[i]; int l = 0; int r = N; while (l < r) { int mid = (l+r)/2; bool in1 = (abs(a[i] + x*mid) + abs(b[i] + y*mid)) <= R; bool in2 = (abs(a[i] + x*(mid+1)) + abs(b[i] + y*(mid+1))) <= R; if (in1 && in2) r = mid; else { if (abs(a[i] + x*mid) + abs(b[i] + y*mid) <= abs(a[i] + x*(mid+1)) + abs(b[i] + y*(mid+1))) { r = mid; } else { l = mid+1; } } } int fst = l; l = 0; r = N; while (l < r) { int mid = (l+r)/2; bool in1 = (abs(a[i] + x*mid) + abs(b[i] + y*mid)) <= R; bool in2 = (abs(a[i] + x*(mid+1)) + abs(b[i] + y*(mid+1))) <= R; if (in1 && in2) l = mid+1; else { if (abs(a[i] + x*mid) + abs(b[i] + y*mid) < abs(a[i] + x*(mid+1)) + abs(b[i] + y*(mid+1))) { r = mid; } else { l = mid+1; } } } int lst = l; if ((abs(a[i] + x*fst) + abs(b[i] + y*fst)) > r) continue; f[fst]++; f[lst+1]--; } int ans = 0; int sum = 0; for (auto& [x, y] : f) { sum += y; ans = max(ans, sum); } cout << ans << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...