fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int ll
  3. using namespace std;
  4. #define rep(i,n) for(int i=0;i<n;i++)
  5. #define per(i,n) for(int i=n-1;i>=0;i--)
  6. #define rng(i,c,n) for(int i=c;i<n;i++)
  7. #define all(a) a.begin(),a.end()
  8. #define sz(a) (int)a.size()
  9. #define fi first
  10. #define se second
  11. #define vec vector
  12. #define pb push_back
  13. typedef long long ll;
  14. typedef vector<int> vi;
  15. typedef pair<int,int> pii;
  16. void print(){cout<<'\n';}
  17. template<class H,class...T>
  18. void print(const H&v,const T&...u){cout<<v<<' ',print(u...);}
  19.  
  20. void slv(){
  21. 	int k,n;
  22. 	cin>>k>>n;
  23.  
  24. 	int ans=0;
  25. 	vi a;
  26. 	vec<pii> e;
  27. 	rep(i,n){
  28. 		char s,t;
  29. 		int x,y;
  30. 		cin>>s>>x>>t>>y;
  31. 		if(s==t){
  32. 			ans+=abs(x-y);
  33. 		}else{
  34. 			ans++;
  35. 			e.pb({x,y});
  36. 			a.pb(x);
  37. 			a.pb(y);
  38. 		}
  39. 	}
  40. 	sort(all(a));
  41.  
  42. 	if(k==2){
  43.  
  44. 		auto g=[&](int xl,int xr){
  45. 			int ret=0;
  46. 			for(auto [x,y]:e){
  47. 				ret+=min(abs(x-xl)+abs(y-xl),abs(x-xr)+abs(y-xr));
  48. 			}
  49. 			// print(xl,xr,ret);
  50. 			return ret;
  51. 		};
  52.  
  53. 		auto f=[&](int pos){
  54. 			int l=pos,r=sz(a)-1;
  55. 			while(r-l>3){
  56. 				int ml=(2*l+r)/3;
  57. 				int mr=(l+2*r)/3;
  58. 				if(g(a[pos],a[ml])<g(a[pos],a[mr])) r=mr;
  59. 				else l=ml;
  60. 			}	
  61.  
  62. 			int ret=1e18;
  63. 			rng(i,l,r+1) ret=min(ret,g(a[pos],a[i]));
  64. 			return ret;
  65. 		};
  66.  
  67. 		int l=0,r=sz(a)-1;
  68. 		while(r-l>3){
  69. 			int ml=(2*l+r)/3;
  70. 			int mr=(l+2*r)/3;
  71. 			if(f(ml)<f(mr)) r=mr;
  72. 			else l=ml;
  73. 		}
  74.  
  75. 		int ad=1e18;
  76. 		rng(i,l,r+1) ad=min(ad,f(i));
  77. 		// print(ad);
  78. 		ans+=ad;
  79. 	}else{
  80. 		rep(i,sz(a)){
  81.             ans+=abs(a[sz(a)/2]-a[i]);
  82.         }
  83. 	}
  84. 	print(ans);
  85. }
  86.  
  87. signed main(){
  88. 	ios::sync_with_stdio(0),cin.tie(0);
  89.  
  90. 	int t;
  91. 	t=1;
  92. 	// cin>>t;
  93.  
  94. 	rep(cs,t){
  95. 		slv();
  96. 	}
  97. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/gYBZtD
language:
C++14 (gcc 8.3)
created:
19 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!