Submission #623529

#	Time	Username	Problem	Language	Result	Execution time	Memory
623529		ipaljak	Wish (LMIO19_noras)	C++14	100 / 100	424 ms	11988 KiB

noras

#include <bits/stdc++.h>

using namespace std;

typedef long long llint;

const int MAXN = 2e5 + 10;

int n;
llint r;

vector<pair<llint, int>> event;

inline double dst(llint x, llint y) {
  return sqrt((double)x * x + (double)y * y);
}

llint closest(llint x, llint y, llint dx, llint dy) {
  llint lo = 0, hi = 1e9;
  while (hi - lo >= 3) {
    llint m1 = lo + (hi - lo) / 3;
    llint m2 = hi - (hi - lo) / 3;
    if (dst(x + m1 * dx, y + m1 * dy) > dst(x + m2 * dx, y + m2 * dy))
      lo = m1;
    else
      hi = m2;
  }
  llint ret = lo;
  for (llint i = lo + 1; i <= hi; ++i)
    if (dst(x + i * dx, y + i * dy) < dst(x + ret * dx, y + ret * dy))
      ret = i;
  return ret;
}

llint find_lo(llint x, llint y, llint dx, llint dy, llint lo, llint hi) {
  while (lo < hi) {
    llint mid = (lo + hi) / 2;
    if (dst(x + mid * dx, y + mid * dy) > r) lo = mid + 1; else hi = mid;
  }
  return lo;
}

llint find_hi(llint x, llint y, llint dx, llint dy, llint lo, llint hi) {
  while (lo < hi) {
    llint mid = (lo + hi) / 2 + 1;
    if (dst(x + mid * dx, y + mid * dy) <= r) lo = mid; else hi = mid - 1;
  }
  return lo;
}

void find_interval(llint a, llint b, llint c, llint d) {
   llint dx = c - a, dy = d - b;
   llint k = closest(a, b, dx, dy);
   //cerr << k << endl;
   //cerr << dst(a + k * dx, b + k * dy) << " " << r << endl;
   if (dst(a + k * dx, b + k * dy) > r) return;
   llint lo = find_lo(a, b, dx, dy, 0, k);
   llint hi = find_hi(a, b, dx, dy, k, 1e9);
   //cerr << lo << " " << hi << endl;
   if (hi < 0LL) return;
   lo = max(lo, 0LL);
   event.emplace_back(lo, 1);
   event.emplace_back(hi + 1, -1);
}

int main(void) {
  scanf("%d%lld", &n, &r);
  for (int i = 0; i < n; ++i) {
    llint a, b, c, d;
    scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
    find_interval(a, b, c, d);
  }

  sort(event.begin(), event.end());

  int curr = 0, sol = 0;
  for (auto &p : event) {
    curr += p.second;
    sol = max(sol, curr);
  }

  printf("%d\n", sol);
  return 0;
}

Compilation message (stderr)

noras.cpp: In function 'int main()':
noras.cpp:67:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |   scanf("%d%lld", &n, &r);
      |   ~~~~~^~~~~~~~~~~~~~~~~~
noras.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |     scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 23 / 23
• Subtask 2: 23 / 23
• Subtask 3: 15 / 15
• Subtask 4: 32 / 32
• Subtask 5: 7 / 7