Submission #770967

#	Time	Username	Problem	Language	Result	Execution time	Memory
770967		dxz05	Wish (LMIO19_noras)	C++17	100 / 100	769 ms	12012 KiB

noras

//#pragma GCC optimize("Ofast,O3,unroll-loops")
//#pragma GCC target("avx,avx2")

#include <bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define bpc(x) __builtin_popcount(x)
#define bpcll(x) __builtin_popcountll(x)
#define MP make_pair
//#define endl '\n'

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

typedef long long ll;
const int MOD = 1e9 + 7;
const int N = 2005;

#define loop for (int it = 0; it < 100; it++)
#define ld __int128

void solve(){
    int n; ll R;
    cin >> n >> R;

    R *= R;

    ld lim = 3e9;

    vector<ld> st, en;
    map<ld, int> mp;

    for (int i = 1; i <= n; i++){
        ll a, b, c, d;
        cin >> a >> b >> c >> d;

        auto dist = [&](ld t) -> ld{
            ld x = c - a, y = d - b;
            x = x * t + a;
            y = y * t + b;
            return x * x + y * y;
        };

        ld t = -1, dt = R + 5;

        ld l = 0, r = lim;
        loop{
            ld m1 = l + (r - l) / 3;
            ld m2 = r - (r - l) / 3;

            ld f1 = dist(m1), f2 = dist(m2);

            if (f1 < dt) t = m1, dt = f1;
            if (f2 < dt) t = m2, dt = f2;

            if (f1 < f2){
                r = m2;
            } else {
                l = m1;
            }

        }

        if (dt > R) continue;

        ld _st = t, _en = t;

        l = 0, r = t;
        loop{
            ld m = (l + r) / 2;
            if (dist(m) <= R){
                _st = min(_st, m);
                r = m;
            } else {
                l = m;
            }
        }

        l = t, r = lim;
        loop{
            ld m = (l + r) / 2;
            if (dist(m) <= R){
                _en = max(_en, m);
                l = m;
            } else {
                r = m;
            }
        }

        st.push_back(_st);
        en.push_back(_en);
        mp[_st] = mp[_en] = 0;
    }

    int z = 0;
    for (auto &now : mp) now.second = ++z;

    vector<int> cnt(z + 2, 0);
    for (int i = 0; i < (int) st.size(); i++){
        cnt[mp[st[i]]]++;
        cnt[mp[en[i]] + 1]--;
    }

    int ans = 0;
    for (int i = 1; i <= z + 1; i++){
        cnt[i] += cnt[i - 1];
        ans = max(ans, cnt[i]);
    }

    cout << ans << endl;

}

int main(){
    clock_t startTime = clock();
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int test_cases = 1;
//    cin >> test_cases;

    for (int test = 1; test <= test_cases; test++){
        //cout << (solve() ? "YES" : "NO") << endl;
        solve();
    }

#ifdef LOCAL
    cerr << "Time: " << int((double) (clock() - startTime) / CLOCKS_PER_SEC * 1000) << " ms" << endl;
#endif

    return 0;
}

Compilation message (stderr)

noras.cpp: In function 'int main()':
noras.cpp:117:13: warning: unused variable 'startTime' [-Wunused-variable]
  117 |     clock_t startTime = clock();
      |             ^~~~~~~~~

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