| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 912412 |
2024-01-19T12:18:25 Z |
vjudge1 |
Wish (LMIO19_noras) |
C++17 |
|
2 ms |
8540 KB |
//Bismillahir-Rahmanir-Rahim
#include <bits/stdc++.h>
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,sse4.1,sse4.2,popcnt,avx,avx2")
#define pb push_back
#define pii pair <int, int>
#define pll pair <long long, long long>
#define pld pair <long double, long double>
#define ll long long
#define ld long double
#define x first
#define y second
#define all(v) v.begin(),v.end()
#define sz(s) (int)s.size()
#define skip continue
#define bpop(x) (ll)__builtin_popcountll(x)
using namespace std;
const int N = 2e5 + 7;
const int K = 400;
const int maxA = 1e7 + 7;
const int inf = 1e9 + 7;
const ll INF = 1e18 + 7;
const ll MOD = 998244353;
const ld eps = 1e-9;
pii dir[] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, R;
pii a[N], cur[N], slope[N];
ld f(int i, int t) {
pii p = {a[i].x + slope[i].x * t, a[i].y + slope[i].y * t};
return sqrt(1.0L * p.x * p.x + 1.0L * p.y * p.y);
}
int t[4 * N], z[4 * N];
void push(int v, int tl, int tr) {
if (z[v] == 0)return;
t[v]++;
if (tl != tr)z[v * 2] |= 1, z[v * 2 + 1] |= 1;
z[v] = 0;
}
void update(int v, int tl, int tr, int l, int r) {
push(v, tl, tr);
if (tr < l || tl > r)return;
if (tl >= l && tr <= r) {
z[v] = 1;
push(v, tl, tr);
return;
}
int mid = (tl + tr) / 2;
update(v * 2, tl, mid, l, r), update(v * 2 + 1, mid + 1, tr, l, r);
t[v] = max(t[v * 2], t[v * 2 + 1]);
}
void solve() {
cin >> n >> R;
for (int i = 1;i <= n;i++)cin >> a[i].x >> a[i].y >> slope[i].x >> slope[i].y, slope[i].x -= a[i].x, slope[i].y -= a[i].y, cur[i] = a[i];
int ans = 0;
for (int i = 1;i <= n;i++) {
int l = 0, r = 1e9 + 7, T = l;
while (r - l >= 5) {
int mid1 = l + (r - l) / 3, mid2 = r - (r - l) / 3;
if (f(i, mid1) > f(i, mid2))l = mid1;
else r = mid2;
}
for (int t = l;t <= r;t++) {
if (f(i, t) < f(i, T))T = t;
}
if (f(i, T) > R)skip;
int L = T, R = T;
l = 0, r = T;
while (l + 1 < r) {
int mid = (l + r) / 2;
if (f(i, mid) <= R)r = mid;
else l = mid;
}
L = r;
l = T, r = 1e9 + 7;
while (l + 1 < r) {
int mid = (l + r) / 2;
if (f(i, mid) <= R)l = mid;
else r = mid;
}
R = l;
update(1, 1, n, L, R);
}
cout << t[1] << '\n';
}
signed main() {
//srand(time(NULL));
ios_base::sync_with_stdio(0);
cin.tie(0);
//freopen("tests.in", "r", stdin);
//freopen("milkorder.out", "w", stdout);
int test = 1;
//cin >> test;
for (int t = 1;t <= test;t++) {
//cout << "Case " << t << ": ";
solve();
}
return 0;
}
Compilation message
noras.cpp: In function 'void solve()':
noras.cpp:63:9: warning: unused variable 'ans' [-Wunused-variable]
63 | int ans = 0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
