Submission #253461

#	Time	Username	Problem	Language	Result	Execution time	Memory
253461		Markoes	Wish (LMIO19_noras)	C++14	100 / 100	190 ms	11376 KiB

noras

#include<bits/stdc++.h>

using namespace std;
int n;
long long R,a,b,c,d,l,r,mid,teng,tmp1,tmp2,opo,bwh,ats;
vector<pair<long long,long long> > v;
long long dist(long long x){
	long long ret;
	ret = (a+c*x)*(a+c*x) + (b+d*x)*(b+d*x);
	return ret;
}

int main(){
	ios_base::sync_with_stdio(NULL);
	cin.tie(0);cout.tie(0);
	cin>>n>>R;
	R *= R;
	for(int i=1;i<=n;i++){
		cin>>a>>b>>c>>d;
		c = c-a;
		d = d-b;
		a -= c;
		b -= d;
		opo = max(abs(c),abs(d));
		l = 1;
		r = 1e9/opo;
		//cout<<r<<endl;
		while(l<=r){
			mid = (l+r)/2;
			tmp1 = dist(mid);
			tmp2 = dist(mid+1);
			if(tmp1>tmp2){
				teng = mid+1;
				l = mid+1;
				//cout<<tmp2<<endl;
			}
			else{
				teng = mid;
				r = mid-1;
				//cout<<tmp1<<endl;
			}
		}
		//cout<<teng<<endl;
		if(dist(teng) > R) continue;
		l = 1;
		r = teng;
		bwh = teng;
		while(l<=r){
			mid = (l+r)/2;
			tmp1 = dist(mid);
			if(tmp1 <= R){
				bwh = mid;
				r = mid-1;
			}
			else{
				l = mid+1;
			}
		}
		
		l = teng;
		r = 1e9/opo;
		ats = teng;
		while(l<=r){
			mid = (l+r)/2;
			tmp1 = dist(mid);
			if(tmp1 <= R){
				ats = mid;
				l = mid+1;
			}
			else{
				r = mid-1;
			}
		}
		
		//cout<<bwh<<' '<<ats<<endl;
		v.push_back(make_pair(bwh,ats));
	}
	
	sort(v.begin(),v.end());
	priority_queue<long long> st;
	int ans=0,cnt;
	
	for(auto x : v){
		//cout<<x.first<<' '<<x.second<<endl;
		while(!st.empty()){
			if(-st.top() < x.first){
				st.pop();
				cnt--;
			}
			else break;
		}
		st.push(-x.second);
		cnt++;
		ans = max(ans,cnt);
	}
	cout<<ans<<endl;
}

Compilation message (stderr)

noras.cpp: In function 'int main()':
noras.cpp:93:6: warning: 'cnt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   cnt++;
   ~~~^~

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