Submission #249106

#	Time	Username	Problem	Language	Result	Execution time	Memory
249106		Gurban	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	77 ms	12512 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ss second
#define ff first
#define N 200005
#define inf 1000000009
#define ll long long
#define pii pair<ll,int>
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
const ll mod = 1e9+7; //998244353;
ll modpow(ll a, ll e) {
	if (e == 0) return 1;
	ll x = modpow(a * a % mod, e >> 1);
	return e & 1 ? x * a % mod : x;
}

int n,k,s,e;
char c,p;
vector <pii>v,adj;
ll ans,add,cep[N],sag[N],num,pos;

int main(){
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	
	scanf("%d%d",&k,&n);
	for(int i = 1;i <= n;i++){
		scanf(" %c%d %c%d",&c,&s,&p,&e);
		if(s < e) swap(s,e);
		if(c == p) add += s-e;
		else v.pb({s,1}),v.pb({e,0}),adj.pb({e,s});
	}
	sort(all(v));
	//for(auto i : v) cout << i.ff << ' ' << i.ss << '\n';
	for(int i = 0;i < sz(v);i++){
		if(i > 0) cep[i] = cep[i-1] + num*(v[i].ff-v[i-1].ff);
		if(v[i].ss == 1) num++;
	}
	num = 0,ans = 1e18;
	for(int i = sz(v)-1;i >= 0;i--){
		if(i < sz(v)-1) sag[i] = sag[i+1] + num*(v[i+1].ff-v[i].ff);
		if(v[i].ss == 0) num++;
		if(ans > cep[i]+sag[i]){
			ans = cep[i]+sag[i];
			pos = v[i].ff;
		}
	}
	ans = 0;
	for(auto i : adj){
		ans += i.ss-i.ff + 1;
		if(pos > i.ss or pos < i.ff) ans += 2ll*min(abs(i.ss-pos),abs(i.ff-pos));
		
	}
	printf("%lld",ans+add);
}
/*
1 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
*/

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&k,&n);
  ~~~~~^~~~~~~~~~~~~~
bridge.cpp:31:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c%d %c%d",&c,&s,&p,&e);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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