Submission #487310

#TimeUsernameProblemLanguageResultExecution timeMemory
487310idasWish (LMIO19_noras)C++17
0 / 100
1 ms460 KiB
#include <bits/stdc++.h> #define FOR(i, begin, end) for(int i = (begin); i < (end); i++) #define FAST_IO ios_base::sync_with_stdio(false); cin.tie(nullptr) #define TSTS int ttt; cin >> ttt; while(ttt--) solve() #define F first #define S second #define PB push_back #define MP make_pair #define sz(x) int((x).size()) using namespace std; typedef pair<int, int> pii; typedef pair<long long, long long> pll; typedef pair<long double, long double> pdd; typedef map<int, int> mii; typedef vector<int> vi; typedef long double ld; typedef long long ll; const int INF=1e9, MOD=1e9+7, mod=98244353; const long long LINF=1e18; void setIO() { FAST_IO; } void setIO(string s) { FAST_IO; freopen((s+".in").c_str(), "r", stdin); freopen((s+".out").c_str(), "w", stdout); } const int N=2e5+10; ll n, R; pair<ll, ll> ini[N], add[N]; ll sq(ll x){return x*x;} pair<ll, ll> getPos(int in, ll t) { return {ini[in].F+add[in].F*t, ini[in].S+add[in].S*t}; } ll calcDist(pair<ll, ll> pos) { return sq(pos.F)+sq(pos.S); } ll getLow(int in) { //davai patikrini po to shita shuda ll l=-1, r=INF; while(l<r-1){ ll m1=(l+r)/2, m2=m1+1; pair<ll, ll> pos1=getPos(in, m1), pos2=getPos(in, m2); ll v1=calcDist(pos1), v2=calcDist(pos2); if(v1<v2) r=m1; else l=m1; } return l+1; } ll lbound(int in, ll x) { ll l=0, r=x; while(l<r){ ll m=(l+r)/2; pair<ll, ll> pos=getPos(in, m); ll dist=calcDist(pos); if(dist>R*R) l=m+1; else r=m; } } ll rbound(int in, ll x) { ll l=x, r=INF; while(l<r){ ll m=(l+r+1)/2; pair<ll, ll> pos=getPos(in, m); ll dist=calcDist(pos); if(dist>R*R) r=m-1; else l=m; } } bool isIn(ll a, ll b) { ll dist=sq(a)+sq(b); return dist<=R*R; } bool bad[N]; int main() { setIO(); cin >> n >> R; ll now=0; FOR(i, 0, n) { ll aa, bb, cc, dd; cin >> aa >> bb >> cc >> dd; if(aa==cc&&bb==dd){ if(isIn(aa, bb)) now++; bad[i]=true; } ini[i]={aa, bb}; add[i]={cc-aa, dd-bb}; } vector<pair<ll, int>> inf; FOR(i, 0, n) { if(bad[i]) continue; ll low=getLow(i); pair<ll, ll> pos=getPos(i, low); ll dist=sq(pos.F)+sq(pos.S); if(dist>R*R) continue; int l=lbound(i, low), r=rbound(i, low); inf.PB({l, 1}); inf.PB({r+1, -1}); } sort(inf.begin(), inf.end()); ll ans=0; for(auto[x, y] : inf){ now+=y; ans=max(ans, now); } cout << ans; }

Compilation message (stderr)

noras.cpp: In function 'll lbound(int, ll)':
noras.cpp:74:1: warning: no return statement in function returning non-void [-Wreturn-type]
   74 | }
      | ^
noras.cpp: In function 'll rbound(int, ll)':
noras.cpp:85:1: warning: no return statement in function returning non-void [-Wreturn-type]
   85 | }
      | ^
noras.cpp: In function 'void setIO(std::string)':
noras.cpp:31:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |     freopen((s+".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
noras.cpp:32:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |     freopen((s+".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...