Submission #1081722

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081722		peacebringer1667	Palembang Bridges (APIO15_bridge)	C++17	31 / 100	82 ms	8632 KiB

bridge

#include<bits/stdc++.h>
#define ll long long
#define ldb long double
#define fi first
#define se second
#define sza(a) (int)a.size()
#define pir pair<int,int>
#define pirll pair<ll,ll>
using namespace std;
const int maxn = 1e5 + 5;

bool type[maxn][2];
int pos[maxn][2];

void input(int n){
	for (int i = 1 ; i <= n ; i++){
		for (int id = 0 ; id <= 1 ; id++){
			char c;int p;
			cin >> c >> p;
			
			type[i][id] = (c == 'A') ? 0 : 1;
			pos[i][id] = p;
		}
	}
}

namespace sub1{
	bool check(int n,int k){
		return (k == 1) && (n <= 1000);
	}
	
	ll calc(int x,int n){
		ll t = 0;
		
		for (int i = 1 ; i <= n ; i++)
		  if (type[i][0] == type[i][1]) t += abs(pos[i][0] - pos[i][1]);
		  else t += abs(pos[i][0] - x) + abs(pos[i][1] - x) + 1;
		return t;
	}
	
	ll solve(int n,int k){
		ll res = LLONG_MAX;
		
		for (int i = 1 ; i <= n ; i++)
		  res = min(res,min(calc(pos[i][0],n),calc(pos[i][1],n)));
		
		return res;
	}
}

namespace sub3{
	bool check(int n,int k){
		return (k == 2 && n <= 100);
	}
	
	ll calc(int x,int y,int n){
		ll t = 0;
		for (int i = 1 ; i <= n ; i++){
			if (type[i][0] == type[i][1]) t += abs(pos[i][0] - pos[i][1]);
			else{
				ll x1 = abs(pos[i][0] - x) + abs(pos[i][1] - x);
				ll x2 = abs(pos[i][0] - y) + abs(pos[i][1] - y); 
				
				t += min(x1,x2) + 1;
			}
		}
		return t;
	}
	
	ll solve(int n,int k){
		vector <int> tmp;
		
		ll res = LLONG_MAX;
		
		for (int i = 1 ; i <= n ; i++){
			tmp.push_back(pos[i][0]);
			tmp.push_back(pos[i][1]);
		}
		sort(tmp.begin(),tmp.end());
		
		for (int x : tmp)
		  for (int y : tmp)
		    if (x <= y) res = min(res,calc(x,y,n));
		return res;
	}
}

namespace sub2{
	bool check(int n,int k){
		return (k == 1);
	}
	
	bool byR(pir x,pir y){
		return (x.se < y.se) || (x.se == y.se && x.fi < y.fi);
	}
	
	vector <pir> L,R;	
    ll simplify(int n){
		int M = n;ll res = 0;
		
		for (int i = 1 ; i <= n ; i++){
			if (type[i][0] == type[i][1])
				res += abs(pos[i][0] - pos[i][1]);
		    else{
		    	if (pos[i][0] > pos[i][1]) swap(pos[i][0],pos[i][1]);
		    	L.push_back({pos[i][0],pos[i][1]});
		    	R.push_back({pos[i][0],pos[i][1]});
			}
		}
		
		
		return res;
	}
	
	ll prelen[maxn],pre[maxn];
	ll suflen[maxn],suf[maxn];
	
	void prepare(){
		sort(L.begin(),L.end(),byR);
		sort(R.begin(),R.end());
		
		for (int i = 0 ; i < L.size() ; i++){
			prelen[i] = ((!i) ? 0 : prelen[i - 1]) + L[i].se - L[i].fi;
			pre[i] = ((!i) ? 0 : pre[i - 1]) + L[i].se + L[i].fi;
		}
		
		for (int i = R.size() - 1; i >= 0; i--){
			suflen[i] = suflen[i + 1] + R[i].se - R[i].fi;
			suf[i] = suf[i + 1] + R[i].fi + R[i].se;
		}
	}
	
	ll calc(int x,ll C){
		ll res = C;
		
		if (x > L[0].se){
			int l = 0,r = L.size() - 1,vt = 0;
			while (l <= r){
				int w = (l + r)/2;
				if (L[w].se < x){
					vt = w;
					l = w + 1;
				}
				else r = w - 1;
			}
			
			res -= prelen[vt];
			res += 2*(ll)x*(ll)(vt + 1) - pre[vt];
		}
		
		if (x < R.back().fi){
			int l = 0,r = R.size() - 1,vt = R.size() - 1;
			
			while (l <= r){
				int w = (l + r)/2;
				if (R[w].fi > x){
					vt = w;
					r = w - 1;
				}
				else l = w + 1;
			}
			
			res -= suflen[vt];
			res += suf[vt] - 2*(ll)x*(ll)(R.size() - vt);
		}
		
		res += L.size();
		
		return res;
	}
	
	ll solve(int n,int k){
		ll res = simplify(n);
		
		if (!L.size()) return res;
		
		prepare();
		
		ll T = LLONG_MAX,C = 0;
		
		for (pir t : L)
		  C += t.se - t.fi;
		
		for (int i = 1 ; i <= n ; i++)
		  T = min(T,min(calc(pos[i][0],C),calc(pos[i][1],C)));
		
		return res + T;
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
//	freopen("B.inp","r",stdin);
//	freopen("B.out","w",stdout);
	int k,n;
	cin >> k >> n;
	input(n);
	
	if (sub1::check(n,k))
	  cout << sub1::solve(n,k) << "\n";else
	
	if (sub2::check(n,k))
	  cout << sub2::solve(n,k) << "\n";else
	  ;
	if (sub3::check(n,k))
	  cout << sub3::solve(n,k);else


	return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'long long int sub2::simplify(int)':
bridge.cpp:99:7: warning: unused variable 'M' [-Wunused-variable]
   99 |   int M = n;ll res = 0;
      |       ^
bridge.cpp: In function 'void sub2::prepare()':
bridge.cpp:122:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |   for (int i = 0 ; i < L.size() ; i++){
      |                    ~~^~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37