Submission #912400

#TimeUsernameProblemLanguageResultExecution timeMemory
912400vjudge1Wish (LMIO19_noras)C++17
0 / 100
2 ms6744 KiB
// #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 = 2e5+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; int pref[maxn*4]; map<int, int>cnt; pii get(int l, int 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(int l1=l, r1=r; l1<=r1;){ int 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(int l1=l, r1=r; l1<=r1;){ int 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(int l1=l, r1=r; l1<=r1;){ int 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(int l1=l, r1=r; l1<=r1;){ int 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){ int mn = min(firt(a[i], x), firt(b[i], y)); int 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){ int mn = firt(a[i], x); v.pb(get(0, mn, i)); v.pb(get(mn+1, 1e9, i)); } else if(b[i]*y < 0){ int mn = firt(b[i], y); v.pb(get(0, mn, i)); v.pb(get(mn+1, 1e9, i)); } else{ v.pb(get(0, 1e9, 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 'pii get(int, int, int)':
noras.cpp:43:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |             int mid = l1+r1>>1;
      |                       ~~^~~
noras.cpp:48:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |             int mid = l1+r1>>1;
      |                       ~~^~~
noras.cpp:55:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |         int mid = l1+r1>>1;
      |                   ~~^~~
noras.cpp:60:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |         int mid = l1+r1>>1;
      |                   ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...