Submission #465471

#	Time	Username	Problem	Language	Result	Execution time	Memory
465471		idas	Wish (LMIO19_noras)	C++11	0 / 100	1 ms	204 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=2e4+100;
int n, r;
vector<pair<pii, pii>> inf;

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

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

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

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

    return left&&right;
}

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

    //TODO MAKE HIGHER
    int l=0, r=N;
    while(l<r){
        int m=(l+r)/2;
        int nx=x+ax*m, ny=y+ay*m;
        if(passed(x, y, nx, ny)) r=m;
        else l=m+1;
    }

    int nx=x+l*ax, ny=y+l*ay;
    if(inside(nx, ny, ax, ay)){
        return true;
    }
    else{
        return false;
    }
}

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

    //TODO MAKE HIGHER
    l=0, r=N;
    while(l<r){
        int m=(l+r)/2;
        int nx=x+ax*m, ny=y+ay*m;
        if(passed(x, y, nx, ny)) r=m;
        else l=m+1;
    }
    times[l+1]--;
}

int main()
{
    FAST_IO;
    cin >> n >> r;
    vi ar;
    FOR(i, 0, n)
    {
        int 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);
    }

    int 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