제출 #329917

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
329917		ChrisGe123	Palembang Bridges (APIO15_bridge)	C++14	0 / 100	1 ms	364 KiB

bridge

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>,
    rb_tree_tag, tree_order_statistics_node_update>;

//g++ -std=c++17 -O2 -fsanitize=undefined /usr/local/Cellar/gcc/10.2.0/include/c++/10.2.0/x86_64-apple-darwin19/bits/stdc++.h
#define maxn 100005
#define mod 1000000007
int n, k;
pair<ll, pair<ll, ll> > interval[maxn]; 
ll ans;


Tree<int> endpoints;

// void setupIO(string s)
// {
// 	ios_base::sync_with_stdio(false);
// 	cin.tie(0);
// 	freopen((s + ".in").c_str(), "r", stdin);
// 	freopen((s + ".out").c_str(), "w", stdout);
// }
int main()
{
	//setupIO("bridges");
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> k >> n;
	int counter = 0;
	ll pre = 0;
	endpoints.clear();
	for (int i=0; i<n; i++)
	{
		char p, q;
		ll s, t;
		cin >> p >> s >> q >> t;
		if (p == q)
		{
			pre += abs(s - t);
		}
		else
		{
			interval[counter++] = make_pair(s+t, make_pair(min(s, t), max(s, t)));
		}
	}
	n = counter;
	if (k == 1)
	{
		ans = 0;
		//we just want to find the median of the endpoints 
		for (int i=0; i<n; i++)
		{
			endpoints.insert(interval[i].second.first);
			endpoints.insert(interval[i].second.second);
		}
		ll x = (*endpoints.find_by_order(n-1) + *endpoints.find_by_order(n)) >> 1;
		for (int i=0; i<n; i++)
		{
			ll l = interval[i].second.first; ll r = interval[i].second.second;
			if (l <= x && x <= r)
			{
				ans += r-l+1;
			}
			else if (x < l)
			{
				ans += 2 * (l -x) + r -l + 1;
			}
			else
			{
				ans += 2 * (x-r) + r - l + 1;
			}
		}
	}
	else
	{
		ans = LLONG_MAX;
		sort(interval, interval+n); //sorted in order of increasing midpoint
		for (int i=0; i<n-1; i++)
		{
			//things 0 to i take the first bridge, i+1 to n-1 take the second bridge
			endpoints.clear();
			for (int j=0; j<=i; j++)
			{
				endpoints.insert(interval[j].second.first);
				endpoints.insert(interval[j].second.second);
			}
			ll x = (*endpoints.find_by_order(i) + *endpoints.find_by_order(i+1)) >> 1;
			endpoints.clear();
			for (int j=i+1; j<n; j++)
			{
				endpoints.insert(interval[j].second.first);
				endpoints.insert(interval[j].second.second);
			}
			ll y = (*endpoints.find_by_order(n-i-2) + *endpoints.find_by_order(n-i-1)) >> 1;
			//cerr << i << endl;
			//cerr << x << " " << y << endl;
			ll temp = 0;
			for (int j=0; j<=i; j++)
			{
				ll l = interval[j].second.first; ll r = interval[j].second.second;
				if (l <= x && x <= r)
				{
					temp += r-l+1;
				}
				else if (x < l)
				{
					temp +=  2 * (l -x) + r -l + 1;
				}
				else
				{
					temp += 2 * (x-r) + r - l + 1;
				}
			}
			for (int j=i+1; j<n; j++)
			{
				ll l = interval[j].second.first; ll r = interval[j].second.second;
				if (l <= y && y <= r)
				{
					temp += r-l+1;
				}
				else if (y < l)
				{
					temp += 2 * (l - y) + r -l + 1;
				}
				else
				{
					temp += 2 * (y-r) + r - l + 1;
				}
			}
			ans = min(ans, temp);
		}
	}
	cout << ans + pre << endl;
}

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