Submission #643324

#TimeUsernameProblemLanguageResultExecution timeMemory
643324pls33Wish (LMIO19_noras)C++17
100 / 100
243 ms19272 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #pragma region dalykai using p32 = pair<int, int>; using p32u = pair<uint32_t, uint32_t>; using p64 = pair<int64_t, int64_t>; using p64u = pair<uint64_t, uint64_t>; using vi16 = vector<int16_t>; using vi16u = vector<uint16_t>; using vi32 = vector<int>; using vi32u = vector<uint32_t>; using vi64 = vector<int64_t>; using vi64u = vector<uint64_t>; using vp32 = vector<p32>; using vp32u = vector<p32u>; using vp64 = vector<p64>; using vp64u = vector<p64u>; using vvi32 = vector<vi32>; using vvi32u = vector<vi32u>; using vvi64 = vector<vi64>; using vvi64u = vector<vi64u>; using vvp32 = vector<vp32>; using vvp32u = vector<vp32u>; using vvp64 = vector<vp64>; using vvp64u = vector<vp64u>; using pf32 = pair<float, float>; using pf64 = pair<double, double>; using pf80 = pair<long double, long double>; using vf32 = vector<float>; using vf64 = vector<double>; using vf80 = vector<long double>; using vpf32 = vector<pf32>; using vpf64 = vector<pf64>; using vpf80 = vector<pf80>; using vvf32 = vector<vf32>; using vvf64 = vector<vf64>; using vvf80 = vector<vf80>; using vvpf32 = vector<vpf32>; using vvpf64 = vector<vpf64>; using vvpf80 = vector<vpf80>; template <typename key, typename val> using ord_map = tree<key, val, less<key>, rb_tree_tag, tree_order_statistics_node_update>; template <typename key> using ord_set = tree<key, null_type, less<key>, rb_tree_tag, tree_order_statistics_node_update>; const int BUF_SZ = 1 << 15; inline namespace fast_in { char buf[BUF_SZ]; int pos; int len; char next_char(FILE *f) { if (pos == len) { pos = 0; len = (int)fread(buf, 1, BUF_SZ, f); if (!len) { return EOF; } } return buf[pos++]; } int read_int(FILE *f) { int x; char ch; int sgn = 1; while (!isdigit(ch = next_char(f))) { if (ch == '-') { sgn *= -1; } } x = ch - '0'; while (isdigit(ch = next_char(f))) { x = x * 10 + (ch - '0'); } return x * sgn; } } /** * @brief gale programos flush_out kviest!! */ inline namespace fast_out { char buf[BUF_SZ]; int pos; void flush_out(FILE *f) { fwrite(buf, 1, pos, f); pos = 0; } void write_char(char c, FILE *f) { if (pos == BUF_SZ) { flush_out(f); } buf[pos++] = c; } void write_int(int x, FILE *f) { static char num_buf[100]; if (x < 0) { write_char('-', f); x *= -1; } int len = 0; for (; x >= 10; x /= 10) { num_buf[len++] = (char)('0' + (x % 10)); } write_char((char)('0' + x), f); while (len) { write_char(num_buf[--len], f); } write_char('\n', f); } } #pragma endregion __int128_t mult(int64_t a, int64_t b) { return __int128_t(a) * b; } __int128_t square(int64_t a) { return mult(a, a); } struct func_t { __int128_t a, b, c; func_t(p64 star, p64 speed) { a = square(speed.first) + square(speed.second); b = 2 * (mult(star.first, speed.first) + mult(star.second, speed.second)); c = square(star.first) + square(star.second); } __int128_t eval(int64_t x) { return a * x * x + b * x + c; } }; bool point_in_circle(p64 p, int64_t radius) { __int128_t x = square(p.first); __int128_t y = square(p.second); __int128_t r = square(radius); return x + y <= r; } int64_t find_peak(func_t func, int64_t right = 1e9 + 1) { int64_t l = -1, r = right; while (r - l > 1) { int64_t mid = (l + r) >> 1; if (func.eval(mid) < func.eval(mid + 1)) { r = mid; } else { l = mid + 1; } } return l + 1; } int64_t find_bound(int64_t peak, int64_t radius, func_t func, bool decrease, int upper = 1e9 + 1) { if (func.eval(peak) > radius * radius) { return -1; } int mult = decrease ? -1 : 1; int64_t res = 0; for (int64_t index = 30; index >= 0; index--) { int64_t cur = peak + mult * (res + (1 << index)); if (cur < 0 || cur > upper) { continue; } __int128_t val = func.eval(cur); if (val > radius * radius) { continue; } res += 1 << index; } return peak + mult * res; } p64 find_range(p64 star, p64 speed, int64_t radius) { func_t distance(star, speed); // int64_t peak = find_peak(distance); int64_t peak_l = -distance.b / (2 * distance.a); int64_t peak_r = peak_l + 1; peak_l = clamp(peak_l, int64_t(0), int64_t(1e9 + 1)); peak_r = clamp(peak_r, int64_t(0), int64_t(1e9 + 1)); int64_t left = find_bound(peak_l, radius, distance, true); int64_t right = find_bound(peak_r, radius, distance, false); if (left == right && right == -1) { return {-1, -1}; } if (left == -1) { return {right, right}; } else if (right == -1) { return {left, left}; } return {left, right}; } int main() { #ifndef _AAAAAAAAA ios_base::sync_with_stdio(false); cin.tie(0); #else freopen("noras.in", "r", stdin); #ifndef __linux__ atexit([]() { freopen("con", "r", stdin); system("pause"); }); #endif #endif int64_t n, radius; cin >> n >> radius; vp64 star(n), speed(n); for (int i = 0; i < n; i++) { int64_t a, b, c, d; cin >> a >> b >> c >> d; star[i] = {a, b}; speed[i] = {c - a, d - b}; } vp64 ranges; for (size_t i = 0; i < n; i++) { p64 time = find_range(star[i], speed[i], radius); if (time == make_pair<int64_t, int64_t>(-1, -1)) { continue; } ranges.emplace_back(time.first, 1); ranges.emplace_back(time.second, -1); } sort(ranges.begin(), ranges.end(), [](p64 a, p64 b) { return (a.first == b.first) ? a.second > b.second : a.first < b.first; }); int64_t count = 0; int64_t result = 0; for (auto &r : ranges) { count += r.second; result = max(count, result); } cout << result << '\n'; return 0; }

Compilation message (stderr)

noras.cpp:8: warning: ignoring '#pragma region dalykai' [-Wunknown-pragmas]
    8 | #pragma region dalykai
      | 
noras.cpp:151: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
  151 | #pragma endregion
      | 
noras.cpp: In function 'int main()':
noras.cpp:301:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int64_t' {aka 'long int'} [-Wsign-compare]
  301 |     for (size_t i = 0; i < n; i++)
      |                        ~~^~~
#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...