Submission #487439

#	Time	Username	Problem	Language	Result	Execution time	Memory
487439		idas	Wish (LMIO19_noras)	C++17	100 / 100	198 ms	15008 KiB

noras

#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=1e8;

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)
{
    if(abs(pos.F)>INF||abs(pos.S)>INF) return -1;
    return sq(pos.F)+sq(pos.S);
}

ll getLow(int in)
{
    //davai patikrini po to shita shuda
    ll l=-1, r=LINF;
    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<0||v2<0){
            r=m1;
            continue;
        }
        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<0){
            r=m;
            continue;
        }
        if(dist>R*R) l=m+1;
        else r=m;
    }
    return l;
}

ll rbound(int in, ll x)
{
    ll l=x, r=LINF;
    while(l<r){
        ll m=(l+r+1)/2;
        pair<ll, ll> pos=getPos(in, m); ll dist=calcDist(pos);
        if(dist<0){
            r=m-1;
            continue;
        }
        if(dist>R*R) r=m-1;
        else l=m;
    }
    return l;
}

int main()
{
    setIO();
    cin >> n >> R;
    ll now=0;
    FOR(i, 0, n)
    {
        ll aa, bb, cc, dd;
        cin >> aa >> bb >> cc >> dd;
        ini[i]={aa, bb}; add[i]={cc-aa, dd-bb};
    }

    vector<pair<ll, int>> inf;
    FOR(i, 0, n)
    {
        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;
}

/*
TESTINGAS:
3 1
0 0 100000 0
0 0 0 0
0 0 0 0
*/

Compilation message (stderr)

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);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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