Submission #329919

#	Time	Username	Problem	Language	Result	Execution time	Memory
329919		ChrisGe123	Palembang Bridges (APIO15_bridge)	C++14	0 / 100	11 ms	620 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<int, 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(make_pair(interval[i].second.first, i));
			endpoints.insert(make_pair(interval[i].second.second, i));
		}
		for (auto k: endpoints)
		{
			cerr << k.first << " ";
		}
		cerr << endl;
		ll x = (endpoints.find_by_order(n-1)->first + endpoints.find_by_order(n)->first) >> 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(make_pair(interval[j].second.first, j));
				endpoints.insert(make_pair(interval[j].second.second, j));
			}
			ll x = (endpoints.find_by_order(i)->first + endpoints.find_by_order(i+1)->first) >> 1;
			endpoints.clear();
			for (int j=i+1; j<n; j++)
			{
				endpoints.insert(make_pair(interval[j].second.first, j));
				endpoints.insert(make_pair(interval[j].second.second, j));
			}
			ll y = (endpoints.find_by_order(n-i-2)->first + endpoints.find_by_order(n-i-1)->first) >> 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;
}

Compilation message (stderr)

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

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