Submission #1164880

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164880		MuhammadSaram	Wish (LMIO19_noras)	C++20	38 / 100	1095 ms	8456 KiB

noras

#include <bits/stdc++.h>

using namespace std;

#define int long long

signed main()
{
	int n,R;
	cin>>n>>R;
	int a[n],b[n],c[n],d[n];
	for (int i=0;i<n;i++)
		cin>>a[i]>>b[i]>>c[i]>>d[i];
	vector<int> v,v1,v2;
	set<int> se;
	for (int i=0;i<n;i++)
	{
		d[i]-=b[i];
		c[i]-=a[i];
		int l,r,l1,r1;
		if (c[i]<0)
		{
			int s=-1,e=1e9;
			while (s+1<e)
			{
				int mid=(s+e)/2;
				if (c[i]*mid+a[i]<=R)
					e=mid;
				else
					s=mid;
			}
			l=e;
			s=0,e=1e9;
			while (s+1<e)
			{
				int mid=(s+e)/2;
				if (c[i]*mid+a[i]>=-R)
					s=mid;
				else
					e=mid;
			}
			r=s;
		}
		else
		{
			int s=-1,e=1e9;
			while (s+1<e)
			{
				int mid=(s+e)/2;
				if (c[i]*mid+a[i]>=-R)
					e=mid;
				else
					s=mid;
			}
			l=e;
			s=0,e=1e9;
			while (s+1<e)
			{
				int mid=(s+e)/2;
				if (c[i]*mid+a[i]<=R)
					s=mid;
				else
					e=mid;
			}
			r=s;
		}
		if (d[i]<0)
		{
			int s=-1,e=1e9;
			while (s+1<e)
			{
				int mid=(s+e)/2;
				if (d[i]*mid+b[i]<=R)
					e=mid;
				else
					s=mid;
			}
			l1=e;
			s=0,e=1e9;
			while (s+1<e)
			{
				int mid=(s+e)/2;
				if (d[i]*mid+b[i]>=-R)
					s=mid;
				else
					e=mid;
			}
			r1=s;
		}
		else
		{
			int s=-1,e=1e9;
			while (s+1<e)
			{
				int mid=(s+e)/2;
				if (d[i]*mid+b[i]>=-R)
					e=mid;
				else
					s=mid;
			}
			l1=e;
			s=0,e=1e9;
			while (s+1<e)
			{
				int mid=(s+e)/2;
				if (d[i]*mid+b[i]<=R)
					s=mid;
				else
					e=mid;
			}
			r1=s;
		}
		l=max(l,l1),r=min(r,r1);
		int l2=-1,r2=-1;
		for (int t=l;t<=r;t++)
		{
			if ((a[i]+t*c[i])*(a[i]+t*c[i])+(b[i]+t*d[i])*(b[i]+t*d[i])<=R*R)
				l2=(l2==-1?t:l2),r2=t;
		}
		if (~l2)
			v.push_back(l2),v1.push_back(r2),v2.push_back(l2),v2.push_back(r2);
	}
	sort(v.begin(),v.end());
	sort(v1.begin(),v1.end());
	sort(v2.begin(),v2.end());
	int ans=0,id=0,id1=0;
	for (int i:v2)
	{
		while (id<v.size() && v[id]<=i)
			id++;
		while (id1<v1.size() && v1[id1]<i)
			id1++;
		ans=max(ans,id-id1);
	}
	cout<<ans<<endl;

	return 0;
}

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