제출 #913262

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
913262		vjudge1	Wish (LMIO19_noras)	C++17	100 / 100	180 ms	15676 KiB

noras

// #pragma GCC target( "sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
// #pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")  
#include<bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define sz(x) (int)x.size()
#define bit(a, i) ((a>>i)&1)

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

const int P = 18;
const int K = 800;
const ll INF = 2e18;
const int inf = 1e9;
const int mod = 1e9+7;
const int maxm = 5e2+10;
const int maxn = 6e5+10;
const int dx[] = {0, 0, -1, 1};
const int dy[] = {1, -1, 0, 0};

int n, sz;
int pref[maxn];
map<ll, int>cnt;
ll rd, a, b, c, d;

ll C(ll a, ll b){
    return a*a+b*b;
}

ld disc(ld a, ld b, ld c, ld d){
    return 2*a*b*c*d-b*b*(c*c-rd*rd)-d*d*(a*a-rd*rd);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    vector<pair<ll, ll>>v;
    cin >> n >> rd;
    set<ll>st;
    for(int i=1; i<=n; i++){
        cin >> a >> c >> b >> d;
        b -= a, d -= c;
        ld D = disc(a, b, c, d);
        if(D < 0) continue;
        //cout << D << " ";
        ld x2 = (-a*b-c*d+sqrtl(D))/(b*b+d*d);
        ld x1 = (-a*b-c*d-sqrtl(D))/(b*b+d*d);
        if(x2 < 0ll) continue;
        ll x = ceil(x1);
        ll y = floor(x2);
        x = max(x, 0ll);
        y = max(y, 0ll);
        v.pb({x, y});
        st.insert(x);
        st.insert(y);
    }
    for(auto to: st) cnt[to] = ++sz;
    for(auto to: v){
        if(to.f == -1) continue;
        pref[cnt[to.f]]++;
        pref[cnt[to.s]+1]--;
    } int ans = 0;
    for(int i=1; i<=sz; i++){
        pref[i] += pref[i-1];
        ans = max(ans, pref[i]);
    } cout << ans;
}

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