Submission #465534

#	Time	Username	Problem	Language	Result	Execution time	Memory
465534		idas	Wish (LMIO19_noras)	C++11	0 / 100	1 ms	332 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 PB push_back
#define F first
#define S second

const int INF=1e9;
const long long LINF=1e18;

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef map<int, int> mii;

const int MX=1e8, N=30000;
ll n, r;
vector<pair<pair<ll, ll>, pair<ll, ll>>> inf;

bool chk(ll x, ll y)
{
    x=abs(x); y=abs(y);
    if(x==r && y==0) return true;
    if(y==r && x==0) return true;
    if(x==0 && y==0) return true;
    if(x>=0 && x<=r-1 && y>=0 && y<=r-1) return true;
    else return false;
}

bool inside(ll x, ll y, ll ax, ll ay)
{
    return chk(x, y)||chk(x-ax, y-ay);
}

bool passed(ll x, ll y, ll nx, ll ny)
{
    bool left=false, right=false;
    if(x<=0){
        if(nx>=0) left=true;
    }
    else if(x>=0){
        if(nx<=0) left=true;
    }
    if(x>=0 && nx>=x) left=true;
    else if(x<=0 && nx<=x) left=true;
    if(y>=0 && ny>=y) right=true;
    else if(y<=0 && ny<=y) right=true;

    if(y<=0){
        if(ny>=0) right=true;
    }
    else if(y>=0){
        if(ny<=0) right=true;
    }

    return left&&right;
}

const int ND=30000;

bool good(int i)
{
    ll x=inf[i].F.F, y=inf[i].F.S, z=inf[i].S.F, w=inf[i].S.S;
    ll ax=z-x, ay=w-y;

    ll l=0, r=N;
    while(l<r){
        ll m=(l+r)/2;
        ll nx=x+ax*m, ny=y+ay*m;
        if(nx<-ND || nx>ND || ny<-ND || ny>ND) r=m;
        if(passed(x, y, nx, ny)&&!chk(nx, ny)) r=m;
        else l=m+1;
    }

    l--;
    ll nx=x+l*ax, ny=y+l*ay;
    if(chk(nx, ny)) return true;
    return false;
}


ll times[N];
void pre(int i)
{
    ll x=inf[i].F.F, y=inf[i].F.S, z=inf[i].S.F, w=inf[i].S.S;
    ll ax=z-x, ay=w-y;
    ll l=0, r=N;
    while(l<r){
        ll m=(l+r)/2;
        ll nx=x+ax*m, ny=y+ay*m;
        if(nx<-ND || nx>ND || ny<-ND || ny>ND) r=m;
        else if(passed(x, y, nx, ny)||chk(nx, ny)) r=m;
        else{
            l=m+1;
        }
    }
    times[l]++;

    l=0; r=N;
    while(l<r){
        ll m=(l+r)/2;
        ll nx=x+ax*m, ny=y+ay*m;
        if(nx<-ND || nx>ND || ny<-ND || ny>ND) r=m;
        else if(passed(x, y, nx, ny) && !chk(nx, ny)) r=m;
        else{
            l=m+1;
        }
    }
    times[l]--;
}

int main()
{
    FAST_IO;
    cin >> n >> r;
    vi ar;
    FOR(i, 0, n)
    {
        ll x, y, z, w;
        cin >> x >> y >> z >> w;
        inf.PB({{x, y}, {z, w}});
        if(inside(x, y, z-x, w-y)||good(i)){
            ar.PB(i);
        }
    }

    for(auto x : ar){
        pre(x);
    }

    ll tot=0, mx=0;
    FOR(i, 0, N)
    {
        tot+=times[i];
        mx=max(mx, tot);
    }
    cout << mx;
}

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