ARC073 E Ball Coloring(700)

帰納法をちゃんと実装する

解法の方針はわかりやすいが、条件整理が面倒

変数名の勉強をしたので、うまく実装できた

1. #include<iostream>
2. #include<algorithm>
3. #include<vector>
4. #include<string>
5. #include<queue>
6. #define lol(i,n) for(int i=0;i<n;i++)
7. #define inf 1000000007
8. typedef long long ll;
9. using namespace std;
10. typedef pair<ll,ll> P;
11. priority_queue<P,vector<P>,greater<P> >Q;
12. vector<ll> v;
13. int main(){
14. int n;
15. ll left=inf,right=0;
16. ll Min_rng=inf,Max_rng=0;
17. ll Min_b=inf;
18. cin>>n;
19. lol(i,n){
20. ll a,b;cin>>a>>b;
21. if(a>b)swap(a,b);
22. left=min(left,a);
23. right=max(right,a);
24. Min_rng=min(Min_rng,a);
25. Max_rng=max(Max_rng,b);
26. Min_b=min(Min_b,b);
27. Q.push(make_pair(a,b));
28. v.push_back(a);
29. }
30. sort(v.begin(),v.end());
31. ll ans=(right-Min_rng)*(Max_rng-Min_b);
32. //cout<<"#"<<left<<" "<<right<<" "<<Min_rng<<" "<<Max_rng<<endl;
33. while(!Q.empty()){
34. ll a=Q.top().first,b=Q.top().second;
35. Q.pop();
36. int it=lower_bound(v.begin(),v.end(),a)-v.begin();
37. it++;
38. if(it==n)break;
39. if(a>Min_b)break;
40. left=min(v[it],Min_b);
41. right=max(right,b);
42. ll tmp=(right-left)*(Max_rng-Min_rng);
43. //cout<<"$"<<" "<<right<<" "<<left<<" "<<tmp<<endl;
44. ans=min(ans,tmp);
45. }
46. cout<<ans<<endl;
47. return 0;
48. }

条件整理大事