Submission #401378

#	Time	Username	Problem	Language	Result	Execution time	Memory
401378		amunduzbaev	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	59 ms	16448 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 pref[N], suf[N], tcnt[N], l[N], r[N];
int pre[N], in[N], pre2[N];

/*

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

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

*/
vpii tt;
vii tmp;

//void dnc(int l = 0, int r = n-1, int lx = 0, int rx = n-1){
	//if(r > l) return;
	//int i = (l + r)>>1;
	//int opt = -1, mn = inf;
	//for(int j=lx;j<=min(rx, j);j++){
		//int m = lb(all(tt), (pii){(tt[i].ff + tt[j].ff + 1)>>1, 0}) - tt.begin();
		//int m2 = --lb(all(tt), (pii){(tt[i].ff + tt[j].ff + 2)>>1, 0}) - tt.begin();
		//assert(abs(m - m2) <= 1);
		//if(umin(mn, pref[j] + suf[i] + (pref[i] - pref[m]) + (suf[j] - suf[m2]) + abs(tt[m].ff - tt[m2].ff) * tcnt[m])) opt = j;
	//} assert(~opt);
	//umin(ans, mn);
	
	//dnc(l, i-1, lx, opt);
	//dnc(i+1, r, opt, rx);
//}

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;
	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, last = 0;
	
	for(int i=0;i<n;){
		int j = i;
		if(last) pref[last] = abs(tt[i-1].ff - tt[i].ff) * cnt * 2 + abs(tt[i-1].ff - tt[i].ff) * cntl + pref[last-1];
		while(j < n && tt[i].ff == tt[j].ff) j++;
		tmp.pb(tt[i].ff);
		while(i < j) { 
			if(tt[i].ss) cntl--, cnt++;
			else cntl++;
			i++;
		} pre[last] = cnt, tcnt[last++] = cntl;
	} 
	
	//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;
	int tll = 0;
	for(int i=0;i<n;){
		int j = i;
		if(tll) suf[last - tll - 1] = abs(tt[i-1].ff - tt[i].ff) * cnt * 2 + abs(tt[i-1].ff - tt[i].ff) * cntl + suf[last - tll];
		while(j < n && tt[i].ff == tt[j].ff) j++;
		while(i < j) { 
			if(!tt[i].ss) cntl--, cnt++;
			else cntl++;
			i++;
		} pre2[last - tll - 1] = cnt, tll++;
	} ans = (n ? inf : 0);
	n = last;
	for(int i=0;i<n;i++) umin(ans, pref[i] + suf[i]);
	
	if(k > 1){ 
		for(int i=0;i<n;i++){
			for(int j=0;j<i;j++){
				int m = lb(all(tmp), (tmp[i] + tmp[j] + 1)>>1) - tmp.begin();
				umin(ans, pref[j] + suf[i] + (pref[i] - pref[m] - pre[m] * abs(tmp[i] - tmp[m]) * 2) + 
				(suf[j] - suf[m] - pre2[m] * abs(tmp[m] - tmp[j]) * 2));
				m = --ub(all(tmp), (tmp[i] + tmp[j])>>1) - tmp.begin();
				umin(ans, pref[j] + suf[i] + (pref[i] - pref[m] - pre[m] * abs(tmp[i] - tmp[m]) * 2) + 
				(suf[j] - suf[m] - pre2[m] * abs(tmp[m] - tmp[j]) * 2));
			}
		}
	} 
	
	
	cout<<res + ans + m<<"\n";
}

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