Submission #679188

#	Time	Username	Problem	Language	Result	Execution time	Memory
679188		penguin133	Palembang Bridges (APIO15_bridge)	C++17	0 / 100	1 ms	340 KiB

bridge

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif

int n, k;
vector<pi> st, en;
bool vis[100005], vis2[100005];
int P[100005], S[100005];
void solve(){
	cin >> k >> n;
	int ans = 0, tmp = 0;
	for(int i=1;i<=n;i++){
		char a, c; int b, d; cin >> a >> b >> c >> d;
		if(a == c)ans += abs(b - d);
		else st.push_back({b, i}), en.push_back({d, i}), tmp += abs(b - d) + 1;
	}
	if(k == 2){
		cout << ans + tmp << '\n';
		return;
	}
	sort(st.begin(), st.end());
	sort(en.begin(), en.end());
	int mn = 1e18;
	int in = 0, cur = 0, heh = 0;
	int lol = 0;
	for(auto [i, j] : st){
		while(in < (int)en.size() && en[in].fi <= i){
			vis2[en[in].se] = 1;
			if(vis[en[in].se] == 1 && vis2[en[in].se] == 1)cur += en[in].fi, heh++;
			in++;
		}	
		vis[j] = 1;
		if(vis[j] == 1 && vis2[j] == 1)heh++, cur += i;
		P[++lol] = 2 * (heh * i - cur);
	}
	in = (int)en.size() - 1, cur = 0, heh = 0;
	for(int i=1;i<=n;i++)vis[i] = vis2[i] = 0;
	for(int a=(int)st.size()-1;a>=0;a--){
		int i = st[a].fi, j = st[a].se;
		while(in >= 0 && en[in].fi >= i){
			vis2[en[in].se] = 1;
			if(vis[en[in].se] == 1 && vis2[en[in].se] == 1)cur += en[in].fi, heh++;
			in--;
		}
		vis[j] = 1;
		if(vis[j] == 1 && vis2[j] == 1)heh++, cur += i;
		S[a + 1] = 2 * (cur - heh * i);
	}
	for(int i=1;i<=(int)st.size();i++)mn = min(mn, P[i] + S[i]);// cout << P[i] << " " << S[i] << '\n';
	//cout << ans << " " << tmp << " " << mn << '\n';
	cout << ans + tmp + mn;
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message (stderr)

bridge.cpp:62:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   62 | main(){
      | ^~~~

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