Submission #912424

#	Time	Username	Problem	Language	Result	Execution time	Memory
912424		vjudge1	Wish (LMIO19_noras)	C++17	100 / 100	522 ms	29928 KiB

noras

//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 = 1e6 + 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());

#define int long long

int n, Rad;
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]);
}
int scan[N];
vector <pii> qs;
void sozhmi() {
    vector <int> v;
    for (auto p : qs)v.pb(p.x), v.pb(p.y);
    sort(all(v));
    map <int, int> id;
    int last = 0, pos = 0;
    for (auto x : v) {
        if (x == last)skip;
        id[x] = ++pos, last = x;
    }
    for (auto &p : qs)p.x = id[p.x], p.y = id[p.y];
}
void solve() {
    cin >> n >> Rad;
    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];
    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) > 1.0L * Rad)skip;
        int L = T, R = T;
        l = -1, r = T;
        while (l + 1 < r) {
            int mid = (l + r) / 2;
            if (f(i, mid) <= 1.0L * Rad) {
                //cout << i << ' ' << mid << ':' << f(i, mid) << "<=" << Rad << '\n';
                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) <= 1.0L * Rad)l = mid;
            else r = mid;
        }
        R = l;
        L++, R++;
        qs.pb({L, R});
        //cout << i << ':' << T << ' ' << L << ' ' << R << '\n';
        //update(1, 1, n, L, R);
        //scan[L]++, scan[R + 1]--;
    }
    sozhmi();
    for (auto p : qs)scan[p.x]++, scan[p.y + 1]--;
    int ans = 0;
    for (int i = 1;i < N;i++)scan[i] += scan[i - 1], ans = max(ans, scan[i]);
    cout << ans;
    //int ans = 0;
    //cout << ans;
}
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;
}

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