Submission #253203

#	Time	Username	Problem	Language	Result	Execution time	Memory
253203		nandonathaniel	Wish (LMIO19_noras)	C++14	100 / 100	296 ms	4736 KiB

noras

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int n;
	vector<pii> segment;
	double r,A,B,C,D,vA,vB;
	cin >> n >> r;
	for(int i=1;i<=n;i++){
		cin >> A >> B >> C >> D;
		vA=C-A;vB=D-B;
		if(A!=C){
			double m=(D-B)/(C-A);
			double c=B-m*A;
			double disk=m*m*c*c-(m*m+1.0)*(c*c-r*r);
			if(disk<0.0)continue;
			disk=sqrt(disk);
			double x1=(-1.0*m*c+disk)/(m*m+1.0),x2=(-1.0*m*c-disk)/(m*m+1.0);
			double time1=(x1-A)/vA+1.0,time2=(x2-A)/vA+1.0;
			if(time2<time1)swap(time1,time2);
			if(time2<1.0)continue;
			if(time1<1.0)time1=1.0;
			int masuk=(int)ceil(time1),keluar=(int)floor(time2)+1;
			if(keluar>masuk){
				segment.push_back({masuk,i});
				segment.push_back({keluar,-i});
			}
		}
		else{
			double val=r*r-A*A;
			if(val<0.0)continue;
			val=sqrt(val);
			double y1=-1.0*val,y2=val;
			double time1=(y1-B)/vB+1.0,time2=(y2-B)/vB+1.0;
			if(time2<time1)swap(time1,time2);
			if(time2<1.0)continue;
			if(time1<1.0)time1=1.0;
			int masuk=(int)ceil(time1),keluar=(int)floor(time2)+1;
			if(keluar>masuk){
				segment.push_back({masuk,i});
				segment.push_back({keluar,-i});
			}
		}
	}
	sort(segment.begin(),segment.end());
	int ans=0,active=0;
	for(auto isi : segment){
		if(isi.second>0)active++;
		else active--;
		ans=max(ans,active);
	}
	cout << ans << '\n';
	return 0;
}

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