| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 375557 |
2021-03-09T14:21:29 Z |
mode149256 |
Wish (LMIO19_noras) |
C++17 |
|
383 ms |
15192 KB |
/*input
2 1
-3 -2 -1 -1
-2 2 -1 1
*/
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
using ll = long long;
using pl = pair<ll, ll>;
struct beam {
pl prad;
pl dxy; // {dx, dy}
};
int N, R;
ll dis(pl a, pl b) { // squared distance
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
// 0th second yra prad
pl getnth(ll n, beam b) {
return {b.prad.x + n * b.dxy.x, b.prad.y + n * b.dxy.y};
}
vector<beam> sk;
ll getINF(beam b) {
return ((ll)1e9) / max(abs(b.dxy.x), abs(b.dxy.y));
}
pl og = {0, 0};
ll closest(beam b) {
ll l = 0;
ll h = getINF(b);
ll m;
while (l < h) {
m = (l + h) / 2;
pl n1 = getnth(m, b);
pl n2 = getnth(m + 1, b);
ll d1 = dis(n1, og);
ll d2 = dis(n2, og);
if (d1 == d2) {
return m;
} else if (d1 < d2) {
h = m;
} else {
l = m + 1;
}
}
return l;
}
ll getFirst(beam b, ll best) {
ll l = 0;
ll h = best;
ll m;
while (l < h) {
m = (l + h) / 2;
pl n1 = getnth(m, b);
ll d1 = dis(n1, og);
if (d1 <= R * R) {
h = m;
} else {
l = m + 1;
}
}
return l;
}
ll getLast(beam b, ll best) {
ll l = best;
ll h = getINF(b);
ll m;
while (l < h) {
m = (l + h + 1) / 2;
pl n1 = getnth(m, b);
ll d1 = dis(n1, og);
if (d1 <= R * R) {
l = m;
} else {
h = m - 1;
}
}
return l;
}
int main() {
cin >> N >> R;
sk.resize(N);
for (int i = 0; i < N; ++i)
{
ll a, b, c, d;
cin >> a >> b >> c >> d;
sk[i] = beam{{a, b}, {c - a, d - b}};
}
vector<pair<int, int>> inter;
for (auto b : sk) {
ll best = closest(b);
if (dis(getnth(best, b), og) > R * R) {
continue;
}
ll pirm = getFirst(b, best);
ll gal = getLast(b, best);
inter.emplace_back(pirm, +1);
inter.emplace_back(gal + 1, -1);
//[pirm, gal]
}
sort(inter.begin(), inter.end());
ll ats = 0;
ll curr = 0;
int j = 0;
while (j < (int)inter.size()) {
ll dabar = inter[j].x;
while (j < (int)inter.size() && inter[j].x == dabar) {
curr += inter[j].y;
j++;
}
ats = max(ats, curr);
}
cout << ats << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
2 ms |
364 KB |
Output is correct |
| 4 |
Correct |
2 ms |
364 KB |
Output is correct |
| 5 |
Correct |
2 ms |
364 KB |
Output is correct |
| 6 |
Correct |
2 ms |
364 KB |
Output is correct |
| 7 |
Correct |
2 ms |
364 KB |
Output is correct |
| 8 |
Correct |
1 ms |
364 KB |
Output is correct |
| 9 |
Correct |
1 ms |
364 KB |
Output is correct |
| 10 |
Correct |
1 ms |
364 KB |
Output is correct |
| 11 |
Correct |
1 ms |
236 KB |
Output is correct |
| 12 |
Correct |
1 ms |
364 KB |
Output is correct |
| 13 |
Correct |
1 ms |
364 KB |
Output is correct |
| 14 |
Correct |
3 ms |
364 KB |
Output is correct |
| 15 |
Correct |
2 ms |
364 KB |
Output is correct |
| 16 |
Correct |
2 ms |
364 KB |
Output is correct |
| 17 |
Correct |
2 ms |
364 KB |
Output is correct |
| 18 |
Correct |
2 ms |
364 KB |
Output is correct |
| 19 |
Correct |
2 ms |
364 KB |
Output is correct |
| 20 |
Correct |
2 ms |
364 KB |
Output is correct |
| 21 |
Correct |
3 ms |
364 KB |
Output is correct |
| 22 |
Correct |
2 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
2 ms |
364 KB |
Output is correct |
| 4 |
Correct |
2 ms |
364 KB |
Output is correct |
| 5 |
Correct |
2 ms |
364 KB |
Output is correct |
| 6 |
Correct |
2 ms |
364 KB |
Output is correct |
| 7 |
Correct |
2 ms |
364 KB |
Output is correct |
| 8 |
Correct |
1 ms |
364 KB |
Output is correct |
| 9 |
Correct |
1 ms |
364 KB |
Output is correct |
| 10 |
Correct |
1 ms |
364 KB |
Output is correct |
| 11 |
Correct |
1 ms |
236 KB |
Output is correct |
| 12 |
Correct |
1 ms |
364 KB |
Output is correct |
| 13 |
Correct |
1 ms |
364 KB |
Output is correct |
| 14 |
Correct |
3 ms |
364 KB |
Output is correct |
| 15 |
Correct |
2 ms |
364 KB |
Output is correct |
| 16 |
Correct |
2 ms |
364 KB |
Output is correct |
| 17 |
Correct |
2 ms |
364 KB |
Output is correct |
| 18 |
Correct |
2 ms |
364 KB |
Output is correct |
| 19 |
Correct |
2 ms |
364 KB |
Output is correct |
| 20 |
Correct |
2 ms |
364 KB |
Output is correct |
| 21 |
Correct |
3 ms |
364 KB |
Output is correct |
| 22 |
Correct |
2 ms |
364 KB |
Output is correct |
| 23 |
Correct |
135 ms |
7264 KB |
Output is correct |
| 24 |
Correct |
133 ms |
7136 KB |
Output is correct |
| 25 |
Correct |
135 ms |
7392 KB |
Output is correct |
| 26 |
Correct |
132 ms |
7264 KB |
Output is correct |
| 27 |
Correct |
136 ms |
6500 KB |
Output is correct |
| 28 |
Correct |
137 ms |
7264 KB |
Output is correct |
| 29 |
Correct |
140 ms |
7520 KB |
Output is correct |
| 30 |
Correct |
141 ms |
7392 KB |
Output is correct |
| 31 |
Correct |
141 ms |
7392 KB |
Output is correct |
| 32 |
Correct |
167 ms |
7520 KB |
Output is correct |
| 33 |
Correct |
166 ms |
7412 KB |
Output is correct |
| 34 |
Correct |
170 ms |
7520 KB |
Output is correct |
| 35 |
Correct |
167 ms |
7520 KB |
Output is correct |
| 36 |
Correct |
178 ms |
7520 KB |
Output is correct |
| 37 |
Correct |
143 ms |
6116 KB |
Output is correct |
| 38 |
Correct |
138 ms |
6116 KB |
Output is correct |
| 39 |
Correct |
139 ms |
6264 KB |
Output is correct |
| 40 |
Correct |
137 ms |
6116 KB |
Output is correct |
| 41 |
Correct |
139 ms |
6116 KB |
Output is correct |
| 42 |
Correct |
141 ms |
6244 KB |
Output is correct |
| 43 |
Correct |
383 ms |
15064 KB |
Output is correct |
| 44 |
Correct |
378 ms |
15068 KB |
Output is correct |
| 45 |
Correct |
382 ms |
15068 KB |
Output is correct |
| 46 |
Correct |
378 ms |
15068 KB |
Output is correct |
| 47 |
Correct |
381 ms |
15068 KB |
Output is correct |
| 48 |
Correct |
358 ms |
14300 KB |
Output is correct |
| 49 |
Correct |
344 ms |
14428 KB |
Output is correct |
| 50 |
Correct |
333 ms |
14428 KB |
Output is correct |
| 51 |
Correct |
331 ms |
14428 KB |
Output is correct |
| 52 |
Correct |
337 ms |
14300 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
2 ms |
364 KB |
Output is correct |
| 4 |
Correct |
2 ms |
364 KB |
Output is correct |
| 5 |
Correct |
2 ms |
364 KB |
Output is correct |
| 6 |
Correct |
2 ms |
364 KB |
Output is correct |
| 7 |
Correct |
2 ms |
364 KB |
Output is correct |
| 8 |
Correct |
1 ms |
364 KB |
Output is correct |
| 9 |
Correct |
1 ms |
364 KB |
Output is correct |
| 10 |
Correct |
1 ms |
364 KB |
Output is correct |
| 11 |
Correct |
1 ms |
236 KB |
Output is correct |
| 12 |
Correct |
1 ms |
364 KB |
Output is correct |
| 13 |
Correct |
1 ms |
364 KB |
Output is correct |
| 14 |
Correct |
3 ms |
364 KB |
Output is correct |
| 15 |
Correct |
2 ms |
364 KB |
Output is correct |
| 16 |
Correct |
2 ms |
364 KB |
Output is correct |
| 17 |
Correct |
2 ms |
364 KB |
Output is correct |
| 18 |
Correct |
2 ms |
364 KB |
Output is correct |
| 19 |
Correct |
2 ms |
364 KB |
Output is correct |
| 20 |
Correct |
2 ms |
364 KB |
Output is correct |
| 21 |
Correct |
3 ms |
364 KB |
Output is correct |
| 22 |
Correct |
2 ms |
364 KB |
Output is correct |
| 23 |
Correct |
1 ms |
364 KB |
Output is correct |
| 24 |
Correct |
2 ms |
364 KB |
Output is correct |
| 25 |
Correct |
2 ms |
364 KB |
Output is correct |
| 26 |
Correct |
2 ms |
364 KB |
Output is correct |
| 27 |
Correct |
2 ms |
364 KB |
Output is correct |
| 28 |
Correct |
2 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
2 ms |
364 KB |
Output is correct |
| 4 |
Correct |
2 ms |
364 KB |
Output is correct |
| 5 |
Correct |
2 ms |
364 KB |
Output is correct |
| 6 |
Correct |
2 ms |
364 KB |
Output is correct |
| 7 |
Correct |
2 ms |
364 KB |
Output is correct |
| 8 |
Correct |
1 ms |
364 KB |
Output is correct |
| 9 |
Correct |
1 ms |
364 KB |
Output is correct |
| 10 |
Correct |
1 ms |
364 KB |
Output is correct |
| 11 |
Correct |
1 ms |
236 KB |
Output is correct |
| 12 |
Correct |
1 ms |
364 KB |
Output is correct |
| 13 |
Correct |
1 ms |
364 KB |
Output is correct |
| 14 |
Correct |
3 ms |
364 KB |
Output is correct |
| 15 |
Correct |
2 ms |
364 KB |
Output is correct |
| 16 |
Correct |
2 ms |
364 KB |
Output is correct |
| 17 |
Correct |
2 ms |
364 KB |
Output is correct |
| 18 |
Correct |
2 ms |
364 KB |
Output is correct |
| 19 |
Correct |
2 ms |
364 KB |
Output is correct |
| 20 |
Correct |
2 ms |
364 KB |
Output is correct |
| 21 |
Correct |
3 ms |
364 KB |
Output is correct |
| 22 |
Correct |
2 ms |
364 KB |
Output is correct |
| 23 |
Correct |
135 ms |
7264 KB |
Output is correct |
| 24 |
Correct |
133 ms |
7136 KB |
Output is correct |
| 25 |
Correct |
135 ms |
7392 KB |
Output is correct |
| 26 |
Correct |
132 ms |
7264 KB |
Output is correct |
| 27 |
Correct |
136 ms |
6500 KB |
Output is correct |
| 28 |
Correct |
137 ms |
7264 KB |
Output is correct |
| 29 |
Correct |
140 ms |
7520 KB |
Output is correct |
| 30 |
Correct |
141 ms |
7392 KB |
Output is correct |
| 31 |
Correct |
141 ms |
7392 KB |
Output is correct |
| 32 |
Correct |
167 ms |
7520 KB |
Output is correct |
| 33 |
Correct |
166 ms |
7412 KB |
Output is correct |
| 34 |
Correct |
170 ms |
7520 KB |
Output is correct |
| 35 |
Correct |
167 ms |
7520 KB |
Output is correct |
| 36 |
Correct |
178 ms |
7520 KB |
Output is correct |
| 37 |
Correct |
143 ms |
6116 KB |
Output is correct |
| 38 |
Correct |
138 ms |
6116 KB |
Output is correct |
| 39 |
Correct |
139 ms |
6264 KB |
Output is correct |
| 40 |
Correct |
137 ms |
6116 KB |
Output is correct |
| 41 |
Correct |
139 ms |
6116 KB |
Output is correct |
| 42 |
Correct |
141 ms |
6244 KB |
Output is correct |
| 43 |
Correct |
383 ms |
15064 KB |
Output is correct |
| 44 |
Correct |
378 ms |
15068 KB |
Output is correct |
| 45 |
Correct |
382 ms |
15068 KB |
Output is correct |
| 46 |
Correct |
378 ms |
15068 KB |
Output is correct |
| 47 |
Correct |
381 ms |
15068 KB |
Output is correct |
| 48 |
Correct |
358 ms |
14300 KB |
Output is correct |
| 49 |
Correct |
344 ms |
14428 KB |
Output is correct |
| 50 |
Correct |
333 ms |
14428 KB |
Output is correct |
| 51 |
Correct |
331 ms |
14428 KB |
Output is correct |
| 52 |
Correct |
337 ms |
14300 KB |
Output is correct |
| 53 |
Correct |
1 ms |
364 KB |
Output is correct |
| 54 |
Correct |
2 ms |
364 KB |
Output is correct |
| 55 |
Correct |
2 ms |
364 KB |
Output is correct |
| 56 |
Correct |
2 ms |
364 KB |
Output is correct |
| 57 |
Correct |
2 ms |
364 KB |
Output is correct |
| 58 |
Correct |
2 ms |
364 KB |
Output is correct |
| 59 |
Correct |
132 ms |
7136 KB |
Output is correct |
| 60 |
Correct |
144 ms |
6628 KB |
Output is correct |
| 61 |
Correct |
146 ms |
6628 KB |
Output is correct |
| 62 |
Correct |
141 ms |
6628 KB |
Output is correct |
| 63 |
Correct |
167 ms |
6900 KB |
Output is correct |
| 64 |
Correct |
161 ms |
6628 KB |
Output is correct |
| 65 |
Correct |
162 ms |
6628 KB |
Output is correct |
| 66 |
Correct |
168 ms |
6756 KB |
Output is correct |
| 67 |
Correct |
163 ms |
6628 KB |
Output is correct |
| 68 |
Correct |
172 ms |
7520 KB |
Output is correct |
| 69 |
Correct |
174 ms |
7456 KB |
Output is correct |
| 70 |
Correct |
175 ms |
7520 KB |
Output is correct |
| 71 |
Correct |
190 ms |
7648 KB |
Output is correct |
| 72 |
Correct |
176 ms |
7520 KB |
Output is correct |
| 73 |
Correct |
137 ms |
6116 KB |
Output is correct |
| 74 |
Correct |
142 ms |
7136 KB |
Output is correct |
| 75 |
Correct |
147 ms |
7284 KB |
Output is correct |
| 76 |
Correct |
143 ms |
6308 KB |
Output is correct |
| 77 |
Correct |
367 ms |
15068 KB |
Output is correct |
| 78 |
Correct |
366 ms |
15068 KB |
Output is correct |
| 79 |
Correct |
372 ms |
15192 KB |
Output is correct |
| 80 |
Correct |
374 ms |
15192 KB |
Output is correct |
| 81 |
Correct |
366 ms |
15068 KB |
Output is correct |
| 82 |
Correct |
349 ms |
14684 KB |
Output is correct |
| 83 |
Correct |
348 ms |
14556 KB |
Output is correct |
| 84 |
Correct |
354 ms |
14556 KB |
Output is correct |
| 85 |
Correct |
345 ms |
14892 KB |
Output is correct |
| 86 |
Correct |
355 ms |
14556 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
2 ms |
364 KB |
Output is correct |
| 4 |
Correct |
2 ms |
364 KB |
Output is correct |
| 5 |
Correct |
2 ms |
364 KB |
Output is correct |
| 6 |
Correct |
2 ms |
364 KB |
Output is correct |
| 7 |
Correct |
2 ms |
364 KB |
Output is correct |
| 8 |
Correct |
1 ms |
364 KB |
Output is correct |
| 9 |
Correct |
1 ms |
364 KB |
Output is correct |
| 10 |
Correct |
1 ms |
364 KB |
Output is correct |
| 11 |
Correct |
1 ms |
236 KB |
Output is correct |
| 12 |
Correct |
1 ms |
364 KB |
Output is correct |
| 13 |
Correct |
1 ms |
364 KB |
Output is correct |
| 14 |
Correct |
3 ms |
364 KB |
Output is correct |
| 15 |
Correct |
2 ms |
364 KB |
Output is correct |
| 16 |
Correct |
2 ms |
364 KB |
Output is correct |
| 17 |
Correct |
2 ms |
364 KB |
Output is correct |
| 18 |
Correct |
2 ms |
364 KB |
Output is correct |
| 19 |
Correct |
2 ms |
364 KB |
Output is correct |
| 20 |
Correct |
2 ms |
364 KB |
Output is correct |
| 21 |
Correct |
3 ms |
364 KB |
Output is correct |
| 22 |
Correct |
2 ms |
364 KB |
Output is correct |
| 23 |
Correct |
135 ms |
7264 KB |
Output is correct |
| 24 |
Correct |
133 ms |
7136 KB |
Output is correct |
| 25 |
Correct |
135 ms |
7392 KB |
Output is correct |
| 26 |
Correct |
132 ms |
7264 KB |
Output is correct |
| 27 |
Correct |
136 ms |
6500 KB |
Output is correct |
| 28 |
Correct |
137 ms |
7264 KB |
Output is correct |
| 29 |
Correct |
140 ms |
7520 KB |
Output is correct |
| 30 |
Correct |
141 ms |
7392 KB |
Output is correct |
| 31 |
Correct |
141 ms |
7392 KB |
Output is correct |
| 32 |
Correct |
167 ms |
7520 KB |
Output is correct |
| 33 |
Correct |
166 ms |
7412 KB |
Output is correct |
| 34 |
Correct |
170 ms |
7520 KB |
Output is correct |
| 35 |
Correct |
167 ms |
7520 KB |
Output is correct |
| 36 |
Correct |
178 ms |
7520 KB |
Output is correct |
| 37 |
Correct |
143 ms |
6116 KB |
Output is correct |
| 38 |
Correct |
138 ms |
6116 KB |
Output is correct |
| 39 |
Correct |
139 ms |
6264 KB |
Output is correct |
| 40 |
Correct |
137 ms |
6116 KB |
Output is correct |
| 41 |
Correct |
139 ms |
6116 KB |
Output is correct |
| 42 |
Correct |
141 ms |
6244 KB |
Output is correct |
| 43 |
Correct |
383 ms |
15064 KB |
Output is correct |
| 44 |
Correct |
378 ms |
15068 KB |
Output is correct |
| 45 |
Correct |
382 ms |
15068 KB |
Output is correct |
| 46 |
Correct |
378 ms |
15068 KB |
Output is correct |
| 47 |
Correct |
381 ms |
15068 KB |
Output is correct |
| 48 |
Correct |
358 ms |
14300 KB |
Output is correct |
| 49 |
Correct |
344 ms |
14428 KB |
Output is correct |
| 50 |
Correct |
333 ms |
14428 KB |
Output is correct |
| 51 |
Correct |
331 ms |
14428 KB |
Output is correct |
| 52 |
Correct |
337 ms |
14300 KB |
Output is correct |
| 53 |
Correct |
132 ms |
7136 KB |
Output is correct |
| 54 |
Correct |
144 ms |
6628 KB |
Output is correct |
| 55 |
Correct |
146 ms |
6628 KB |
Output is correct |
| 56 |
Correct |
141 ms |
6628 KB |
Output is correct |
| 57 |
Correct |
167 ms |
6900 KB |
Output is correct |
| 58 |
Correct |
161 ms |
6628 KB |
Output is correct |
| 59 |
Correct |
162 ms |
6628 KB |
Output is correct |
| 60 |
Correct |
168 ms |
6756 KB |
Output is correct |
| 61 |
Correct |
163 ms |
6628 KB |
Output is correct |
| 62 |
Correct |
172 ms |
7520 KB |
Output is correct |
| 63 |
Correct |
174 ms |
7456 KB |
Output is correct |
| 64 |
Correct |
175 ms |
7520 KB |
Output is correct |
| 65 |
Correct |
190 ms |
7648 KB |
Output is correct |
| 66 |
Correct |
176 ms |
7520 KB |
Output is correct |
| 67 |
Correct |
137 ms |
6116 KB |
Output is correct |
| 68 |
Correct |
142 ms |
7136 KB |
Output is correct |
| 69 |
Correct |
147 ms |
7284 KB |
Output is correct |
| 70 |
Correct |
143 ms |
6308 KB |
Output is correct |
| 71 |
Correct |
367 ms |
15068 KB |
Output is correct |
| 72 |
Correct |
366 ms |
15068 KB |
Output is correct |
| 73 |
Correct |
372 ms |
15192 KB |
Output is correct |
| 74 |
Correct |
374 ms |
15192 KB |
Output is correct |
| 75 |
Correct |
366 ms |
15068 KB |
Output is correct |
| 76 |
Correct |
349 ms |
14684 KB |
Output is correct |
| 77 |
Correct |
348 ms |
14556 KB |
Output is correct |
| 78 |
Correct |
354 ms |
14556 KB |
Output is correct |
| 79 |
Correct |
345 ms |
14892 KB |
Output is correct |
| 80 |
Correct |
355 ms |
14556 KB |
Output is correct |
| 81 |
Correct |
1 ms |
364 KB |
Output is correct |
| 82 |
Correct |
2 ms |
364 KB |
Output is correct |
| 83 |
Correct |
2 ms |
364 KB |
Output is correct |
| 84 |
Correct |
2 ms |
364 KB |
Output is correct |
| 85 |
Correct |
2 ms |
364 KB |
Output is correct |
| 86 |
Correct |
2 ms |
364 KB |
Output is correct |
| 87 |
Incorrect |
186 ms |
7020 KB |
Output isn't correct |
| 88 |
Halted |
0 ms |
0 KB |
- |
