Submission #969738

#	Time	Username	Problem	Language	Result	Execution time	Memory
969738		blacktulip	Wish (LMIO19_noras)	C++17	100 / 100	205 ms	24492 KiB

noras

#include <bits/stdc++.h>

using namespace std;

typedef long long lo; 

#define fi first
#define se second
#define endl "\n"
#define int long long
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)
#define _ << " " <<

const lo inf = 1000000000;
const lo li = 500005;
const lo mod = 1000000007;

int n,m,a[li],k,flag,t,x[li],y[li],xx[li],yy[li];
int cev;
string s;
vector<pair<int,int>> v;

inline __int128 d(int i,__int128 t){
	return (x[i]+(xx[i]-x[i])*t)*(x[i]+(xx[i]-x[i])*t)+(y[i]+(yy[i]-y[i])*t)*(y[i]+(yy[i]-y[i])*t);
}

inline int cp(int i){
	int bas=0;
	int son=100000000000;
	while(bas<son){
		if(d(i,ort)<d(i,ort+1))son=ort;
		else bas=ort+1;
		//~ cout<<bas _ son<<endl;
	}
	if(d(i,bas)<d(i,son))return bas;
	return son;
}

int32_t main(void){
	fio();
	cin>>n>>k;
	FOR{
		cin>>x[i]>>y[i]>>xx[i]>>yy[i];
		int tut=cp(i);
		int bas=tut;
		int son=100000000000;
		while(bas<=son){
			if(d(i,ort)<=k*k)bas=ort+1;
			else son=ort-1;
		}
		int r=son;
		bas=0;
		son=tut;
		while(bas<=son){
			if(d(i,ort)<=k*k)son=ort-1;
			else bas=ort+1;
		}
		int l=bas;
		if(l<=r)v.pb({l,r});
		//~ cout<<i _ l _ r<<endl;
	}
	sort(v.begin(),v.end());
	priority_queue<int> pq;
	for(auto go:v){
		while(pq.size() && -pq.top()<go.fi)pq.pop();
		pq.push(-go.se);
		cev=max(cev,(int)pq.size());
	}
	cout<<cev<<endl;
	return 0;
}

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