Submission #249555

#	Time	Username	Problem	Language	Result	Execution time	Memory
249555		AMO5	Palembang Bridges (APIO15_bridge)	C++17	0 / 100	2 ms	512 KiB

bridge

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define eb emplace_back
#define mt make_tuple
#define all(x) (x).begin(), (x).end()  
#define sz(x) int(x.size()) 
#define MOD 1000000007

typedef long long ll;
typedef pair <int, int> ii;
typedef pair <ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef long double ld;

const ll INF=LLONG_MAX;
const int mxn=1e6+5;
bool DEBUG=0;
int n,k;
bool vis[mxn];
char hs[mxn],of[mxn];
ll hos[mxn],off[mxn];
vi coor;
vector<ii>str;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
	cin >> k >> n;
	ll ans = 0ll;
	for(int i=0; i<n; i++){
		cin >> hs[i] >> hos[i] >> of[i] >> off[i];
		if(hs[i]==of[i]){
			ans += ll(abs(hos[i]-off[i]));
		}else{
			if(hos[i]>off[i])swap(hos[i],off[i]);
			ans+=off[i]-hos[i]+1ll;
			str.eb(hos[i],off[i]);
			coor.eb(hos[i]);
			coor.eb(off[i]);
		}
	}
	sort(all(coor));
	//k=1
	int bridge1=coor[sz(str)-1],bridge2=coor[sz(str)];
	ll res1=0ll,res2=0ll;
	for(int i=0; i<sz(str); i++){
		if(bridge1<str[i].fi){
			res1 += 2ll*(str[i].fi-bridge1);
		}else if(bridge1>str[i].se){
			res1 += 2ll*(bridge1-str[i].se);
		}
		if(bridge2<str[i].fi){
			res2 += 2ll*(str[i].fi-bridge2);
		}else if(bridge2>str[i].se){
			res2 += 2ll*(bridge2-str[i].se);
		}
	}
	ans += min(res1,res2);
	cout << ans << '\n';
}
	
// READ & UNDERSTAND
// ll, int overflow, array bounds, memset(0)
// special cases (n=1?), n+1 (1-index)
// do smth instead of nothing & stay organized
// WRITE STUFF DOWN

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