제출 #401361

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
401361		amunduzbaev	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	56 ms	10572 KiB

bridge

/* made by amunduzbaev */
 
#include <bits/stdc++.h>
 
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
//using namespace __gnu_pbds;
 
#define ff first
#define vv vector
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define sz(x) (int)x.size()
#define tut(x) array<int, x> 
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define NeedForSpeed ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii; 
typedef vector<int> vii;
typedef vector<pii> vpii;
 
template<class T> bool umin(T& a, const T& b) { return a > b? a = b, true:false; }
template<class T> bool umax(T& a, const T& b) { return a < b? a = b, true:false; }
//void usaco(string s) { freopen((s+".in").c_str(),"r",stdin);  
	//freopen((s+".out").c_str(),"w",stdout); }
//template<class T> tree<T, 
//less<T>, null_type, rb_tree_tag, 
//tree_order_statistics_node_update> ordered_set;
 
const int N = 2e5+5;
const int mod = 1e9+7;
const ll inf = 1e18;
const ld Pi = acos(-1);
 
#define MULTI 0
int n, m, k, ans, q, res, a[N];
int l[N], r[N];
int pref[N], suf[N];

/*

1 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7

*/

void solve(int t_case){
	cin>>k>>n;
	for(int i=0, last = 0;i<n;i++){
		char s1, s2; int p1, p2; 
		cin>>s1>>p1>>s2>>p2;
		if(s1 == s2) res += abs(p1 - p2);
		else l[last] = min(p1, p2), r[last] = max(p1, p2), last++, m = last;
	} n = m;
	vpii tt;
	for(int i=0;i<n;i++){
		tt.pb({l[i], 0});
		tt.pb({r[i], 1});
	} sort(all(tt));
	
	n = sz(tt);
	int cost = 0, cnt = 0, cntl = 0;
	for(int i=0;i<n;){
		int j = i;
		if(i) pref[i] = abs(tt[i-1].ff - tt[i].ff) * cnt * 2 + abs(tt[i-1].ff - tt[i].ff) * cntl + pref[i-1];
		while(j < n && tt[i].ff == tt[j].ff) pref[j] = pref[i], j++;
		while(i < j) { 
			if(tt[i].ss) cntl--, cnt++;
			else cntl++;
			i++;
		}
	} 
	
	//for(auto x : tt) cout<<x.ff<<" ";
	//cout<<"\n";
	//for(auto x : tt) cout<<x.ss<<" ";
	//cout<<"\n";
	
	reverse(all(tt));
	cnt = cntl = cost = 0;
	for(int i=0;i<n;){
		int j = i;
		if(i) suf[n - i - 1] = abs(tt[i-1].ff - tt[i].ff) * cnt * 2 + abs(tt[i-1].ff - tt[i].ff) * cntl + suf[n - i];
		while(j < n && tt[i].ff == tt[j].ff) suf[n - j - 1] = suf[n - i - 1], j++;
		while(i < j) { 
			if(!tt[i].ss) cntl--, cnt++;
			else cntl++;
			i++;
		}
	} ans = (n ? inf : 0);
	
	for(int i=0;i<n;i++) umin(ans, pref[i] + suf[i]);
	//for(int i=0;i<n;i++) cout<<pref[i]<<" ";
	//cout<<"\n";
	//for(int i=0;i<n;i++) cout<<suf[i]<<" ";
	//cout<<"\n";
	if(k == 1) { cout<<res + ans + m<<"\n"; return; }
}

signed main(){ 
	
	NeedForSpeed
	if(!MULTI) {
		solve(1);
	} else {
		int t; cin>>t;
		for(int t_case = 1; t_case <= t; t_case++) solve(t_case);
	} return 0;
}

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