Submission #912406

#	Time	Username	Problem	Language	Result	Execution time	Memory
912406		vjudge1	Wish (LMIO19_noras)	C++17	0 / 100	2 ms	8792 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 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};

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

pair<ll, ll> get(ll l, ll r, int i){
    if(l > r) return {-1, -1};
    ll x = c[i]-a[i], y = d[i]-b[i], val=0;
    if(abs(a[i]+x*l) > abs(a[i]+x*(l+1))) val -= abs(x);
    else val += abs(x);
    if(abs(b[i]+y*l) > abs(b[i]+y*(l+1))) val -= abs(y);
    else val += abs(y);
    ll sum = abs(a[i]+x*l) + abs(b[i]+y*l);
    int L = -1, R = -1;
    if(val < 0){
        for(ll l1=l, r1=r; l1<=r1;){
            ll mid = l1+r1>>1;
            if(sum+val*(mid-l) > rd) l1 = mid + 1;
            else r1 = mid - 1, L = mid;
        } if(L == -1) return {-1, -1};
        for(ll l1=l, r1=r; l1<=r1;){
            ll mid = l1+r1>>1;
            if(sum+val*(mid-l) < -rd) r1 = mid - 1;
            else l1 = mid + 1, R = mid;
        } if(R == -1) return {-1, -1};
        return {L, R};
    }
    for(ll l1=l, r1=r; l1<=r1;){
        ll mid = l1+r1>>1;
        if(sum+val*(mid-l) < -rd) l1 = mid + 1;
        else r1 = mid - 1, L = mid;
    } if(L == -1) return {-1, -1};
    for(ll l1=l, r1=r; l1<=r1;){
        ll mid = l1+r1>>1;
        if(sum+val*(mid-l) > rd) r1 = mid - 1;
        else l1 = mid + 1, R = mid;
    } if(R == -1) return {-1, -1};
    return {L, R};
}

ll firt(ll x, ll c){
    return abs(x)/abs(c);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    vector<pii>v;
    cin >> n >> rd;
    for(int i=1; i<=n; i++){
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        ll x = c[i]-a[i], y = d[i]-b[i];
        if(a[i]*x < 0 && b[i]*y < 0){
            ll mn = min(firt(a[i], x), firt(b[i], y));
            ll mx = max(firt(a[i], x), firt(b[i], y));
            v.pb(get(0, mn, i));
            v.pb(get(mn+1, mx, i));
            v.pb(get(mx+1, 1e9, i));
        } else if(a[i]*x < 0){
            ll mn = firt(a[i], x);
            v.pb(get(0, mn, i));
            v.pb(get(mn+1, 1e9, i));
        } else if(b[i]*y < 0){
            ll mn = firt(b[i], y);
            v.pb(get(0, mn, i));
            v.pb(get(mn+1, 1e9, i));
        } else{
            v.pb(get(0, 1e18, i));
        }
    }
    set<ll>st;
    for(auto to: v){
        if(to.f == -1) continue;
        st.insert(to.f);
        st.insert(to.s);
    }
    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=0; i<=sz; i++){
        if(i) pref[i] += pref[i-1];
        ans = max(ans, pref[i]);
    } cout << ans;
}

Compilation message (stderr)

noras.cpp: In function 'std::pair<long long int, long long int> get(ll, ll, int)':
noras.cpp:43:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |             ll mid = l1+r1>>1;
      |                      ~~^~~
noras.cpp:48:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |             ll mid = l1+r1>>1;
      |                      ~~^~~
noras.cpp:55:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |         ll mid = l1+r1>>1;
      |                  ~~^~~
noras.cpp:60:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |         ll mid = l1+r1>>1;
      |                  ~~^~~

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