Submission #331021

#	Time	Username	Problem	Language	Result	Execution time	Memory
331021		ChrisGe123	Palembang Bridges (APIO15_bridge)	C++14	63 / 100	2090 ms	15340 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<pair<ll, int> > lendpoints;
Tree<pair<ll, int> > rendpoints;

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;
	lendpoints.clear();
	rendpoints.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
		{
			ll l = min(s, t);
			ll r = max(s, t);
			interval[counter++] = make_pair(s+t, make_pair(l, r));
			pre += r - l + 1;
		}
	}
	//use the below version to make it easier to randomly generate test cases 
	// for (int i=0; i<n; i++)
	// {
	// 	ll s, t;
	// 	cin >> s >> t;
	// 	ll l = min(s, t);
	// 	ll r = max(s, t);
	// 	interval[counter++] = make_pair(s+t, make_pair(l, r));
	// 	pre += r - l + 1;
	// }
	n = counter;
	ans = 0;
	//we just want to find the median of the endpoints 
	sort(interval, interval+n);
	for (int i=0; i<n; i++)
	{
		rendpoints.insert(make_pair(interval[i].second.first, 2*i));
		rendpoints.insert(make_pair(interval[i].second.second, 2*i+1));
	}
	ll xone = rendpoints.find_by_order(n-1)->first;
	//cerr << x << endl;
	for (int i=0; i<n; i++)
	{
		ll l = interval[i].second.first; ll r = interval[i].second.second;
		if (l <= xone && xone <= r)
		{
			continue;
		}
		else if (xone < l)
		{
			ans += 2 * (l-xone);
		}
		else
		{
			ans += 2 * (xone-r);
		} 
	}
	if (k == 2)
	{
		 //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
			lendpoints.insert(make_pair(interval[i].second.first, 2*i));
			lendpoints.insert(make_pair(interval[i].second.second, 2*i+1));
			ll x = lendpoints.find_by_order(i)->first;
			rendpoints.erase(make_pair(interval[i].second.first, 2*i));
			rendpoints.erase(make_pair(interval[i].second.second, 2*i+1));
			ll y = rendpoints.find_by_order(n-i-2)->first;
			
			// cerr << endl;
			// 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)
				{
					continue;
				}
				else if (x < l)
				{
					temp +=  2 * (l-x);
				}
				else
				{
					temp += 2 * (x-r);
				}
			}
			//cerr << temp << endl;
			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)
				{
					continue;
				}
				else if (y < l)
				{
					temp += 2 * (l-y);
				}
				else
				{
					temp += 2 * (y-r);
				}
			}
			//cerr << temp << endl;
			ans = min(ans, temp);
		}
	}
	cout << ans + pre << endl;
}

Compilation message (stderr)

bridge.cpp: In function 'void setupIO(std::string)':
bridge.cpp:25:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   25 |  freopen((s + ".in").c_str(), "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:26:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   26 |  freopen((s + ".out").c_str(), "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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