Submission #435406

#	Time	Username	Problem	Language	Result	Execution time	Memory
435406		sinamhdv	Palembang Bridges (APIO15_bridge)	C++11	49 / 100	92 ms	3176 KiB

bridge

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1e9 + 100;
const ll LINF = 1e18 + 100;

#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define FOR(i, a, b) for (int i = (a); i < (int)(b); i++)
#define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define endl '\n'

#define MAXN 1050

int k, n;
int z1[MAXN], z2[MAXN], lft[MAXN], rgt[MAXN];
ll ans, sig;
vector<int> cor;
vector<int> beg[2 * MAXN], fin[2 * MAXN];
vector<int> goback[2 * MAXN];

int32_t main(void)
{
	fast_io;
	cin >> k >> n;
	FOR(i, 0, n)
	{
		char c;
		cin >> c;
		z1[i] = c - 'A';
		cin >> lft[i] >> c;
		z2[i] = c - 'A';
		cin >> rgt[i];
		if (lft[i] > rgt[i]) swap(lft[i], rgt[i]);
		ans += rgt[i] - lft[i] + (z1[i] != z2[i]);
		cor.pb(lft[i]);
		cor.pb(rgt[i]);
		sig += lft[i];
	}

	dbgr(z1, z1 + n);
	dbgr(z2, z2 + n);

	ll bksum = 0, bkcnt = 0;
	ll fwsum = 0, fwcnt = 0;

	sort(all(cor));
	cor.resize(unique(all(cor)) - cor.begin());
	FOR(i, 0, n)
	{
		lft[i] = lower_bound(all(cor), lft[i]) - cor.begin();
		rgt[i] = lower_bound(all(cor), rgt[i]) - cor.begin();
		if (z1[i] == z2[i]) continue;
		beg[lft[i]].pb(i);
		fin[rgt[i]].pb(i);
		fwsum += cor[lft[i]];
		fwcnt++;
	}

	FOR(i, 0, (int)cor.size())
	{
		for (int u : beg[i])
		{
			fwcnt--;
			fwsum -= cor[lft[u]];
			dbg(u);
		}

	/*	if (i == 4)
		{
			dbg(bkcnt);
			dbg(fwcnt);
			dbg(bksum);
			dbg(fwsum);
			dbg(cor[i]);
		}*/

		sig = min(sig, cor[i] * bkcnt - bksum + fwsum - cor[i] * fwcnt);
		if (k == 2)
		{

			ll res = LINF;
			ll _fwsum = fwsum, _fwcnt = fwcnt;
			ll midsum = 0, midcnt = 0;
			ll midbksum = 0;

			FOR(j, i + 1, (int)cor.size())
			{
				for (int u : beg[j])
				{
					fwcnt--;
					fwsum -= cor[lft[u]];
				}
				for (int u : goback[j])
				{
					midbksum += cor[lft[u]] - cor[i];
					midcnt--;
					midsum -= cor[rgt[u]];
				}

				res = min(res, midbksum + cor[j] * midcnt - midsum + fwsum - cor[j] * fwcnt);

				for (int u : fin[j]) if (lft[u] > i)
				{
					midcnt++;
					midsum += cor[rgt[u]];
					// assign go back
					int pos = lower_bound(all(cor), cor[rgt[u]] + cor[lft[u]] - cor[i]) - cor.begin();
					if (pos < (int)cor.size())
						goback[pos].pb(u);
				}
			}

			FOR(j, 0, 2 * MAXN) goback[j].clear();
			fwsum = _fwsum;
			fwcnt = _fwcnt;
	
			res += cor[i] * bkcnt - bksum;
			sig = min(sig, res);
		}

		for (int u : fin[i])
		{
			bkcnt++;
			bksum += cor[rgt[u]];
		}
	}

	ans += 2 * sig;
	cout << ans << endl;
	
	return 0;
}

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