Submission #264921

#	Time	Username	Problem	Language	Result	Execution time	Memory
264921		Berted	Palembang Bridges (APIO15_bridge)	C++11	63 / 100	2097 ms	29124 KiB

bridge

#include <iostream>
#include <vector>
#include <algorithm>
#include <assert.h>
#define vi vector<int>
#define pub push_back
#define pii pair<int, int>
#define fst first
#define snd second
#define ll long long
using namespace std;
 
const int INF = 1e9;
const ll INF2 = 1e18;
 
int C2[200001], C2sz = 0;
 
struct BIT
{
	ll fwk[2][200001], ar[2][200001], sum[2];
	inline void upd(int t, int x, int v)
	{
		ar[t][x] += v;
		for (; x < C2sz; x += x & (-x)) {fwk[t][x] += v;}
		sum[t] += v;
	}
	inline ll qry(int t, int x)
	{
		ll ret = 0; 
		for (; x; x -= x & (-x)) {ret += fwk[t][x];}
		return ret;
	}
};
 
int k, n, lfm, rgm; ll opt;
int C[200001], Csz = 0;
pii seg[2][100001]; int segSz[2]; 
ll res = 0;
BIT L[2], R[2];
 
inline void prep() 
{
	sort(C2, C2 + C2sz);
	C2sz = unique(C2, C2 + C2sz) - C2;
}
 
inline int getCoord(int x)
{
	return prev(upper_bound(C2, C2 + C2sz, x)) - C2;
}
 
inline ll eval(int k, int gx, int x)
{
	if (x < 0 || x > INF) return INF2;
	if (gx == -1) {gx = getCoord(x);}
	return L[k].qry(0, gx) * x - L[k].qry(1, gx) + (R[k].sum[1] - R[k].qry(1, gx)) - x * (R[k].sum[0] - R[k].qry(0, gx));
}
 
inline ll solve(int t, int lf, int rg)
{
	int M;
	while (rg - lf > 3)
	{
		int M = lf + ((rg - lf) >> 1);
		int gx = getCoord(M + 1);
		ll v = -L[t].qry(0, gx) + (R[t].sum[0] - R[t].qry(0, gx)); 
		if (C2[gx] == M + 1)
		{
			v += (L[t].ar[1][gx] + R[t].ar[1][gx] - L[t].ar[0][gx] * M - R[t].ar[0][gx] * M);
		}
		if (M + 1 > INF || v < 0) {rg = M + 1;}
		else {lf = M;}
	}
	int ans = lf;
	for (int i = lf + 1; i <= rg; i++)
	{
		if (eval(t, -1, i) < eval(t, -1, ans)) {ans = i;}
	}
	return eval(t, -1, ans);
}
 
inline ll solve2(int t, int lf, int rg)
{
	while (rg - lf > 3)
	{
		int M = lf + ((rg - lf) >> 1);
		int gx = getCoord(M + 1);
		ll v = -L[t].qry(0, gx) + (R[t].sum[0] - R[t].qry(0, gx)); 
		if (C2[gx] == M + 1)
		{
			v += (L[t].ar[1][gx] + R[t].ar[1][gx] - L[t].ar[0][gx] * M - R[t].ar[0][gx] * M);
		}
		if (M + 1 > INF || v < 0) {rg = M + 1;}
		else {lf = M;}
	}
	int ans = lf;
	for (int i = lf + 1; i <= rg; i++)
	{
		if (eval(t, -1, i) < eval(t, -1, ans)) {ans = i;}
	}
	return ans;
}
 
inline ll eval2(int x, int l, int r)
{
	if (l < 0 || r > INF || l > r) return INF2; 
	if (r < lfm) {return eval(0, -1, x) + eval(1, -1, r);}
	else if (l > rgm) {return eval(0, -1, x) + eval(1, -1, l);}
	else {return eval(0, -1, x) + opt;}
}
 
int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	//freopen("bridges.in", "r", stdin);
	cin >> k >> n;
	C2[C2sz++] = -1;
	for (int i = 0; i < n; i++)
	{
		char c1, c2; int p1, p2; cin >> c1 >> p1 >> c2 >> p2;
		if (p1 > p2) swap(p1, p2);
		res += p2 - p1;
		if (c1 != c2) 
		{
			res++;
			seg[0][segSz[0]++] = {p1, p2};
			seg[1][segSz[1]++] = {p1 + p2, segSz[0] - 1};
			C[Csz++] = p1 + p2;
			C2[C2sz++] = p1;
			C2[C2sz++] = p2;
		}
	}
	prep();
	//cout << res << "\n";
	if (k == 1)
	{
		for (int i = 0; i < segSz[0]; i++)
		{
			int gx = getCoord(seg[0][i].snd);
			L[0].upd(0, gx, 1);
			L[0].upd(1, gx, seg[0][i].snd);
			gx = getCoord(seg[0][i].fst);
			R[0].upd(0, gx, 1);
			R[0].upd(1, gx, seg[0][i].fst);
		}
		cout << res + 2 * solve(0, 0, INF) << "\n";
	}
	else
	{
		sort(seg[1], seg[1] + segSz[1]);
		C[Csz++] = 0; C[Csz++] = 2 * INF; C[Csz++] = 2 * INF + 1;
		sort(C, C + Csz); 
		Csz = unique(C, C + Csz) - C;
		int j = 0;
		for (int i = 0; i < segSz[0]; i++)
		{
			int gx = getCoord(seg[0][i].snd);
			L[1].upd(0, gx, 1);
			L[1].upd(1, gx, seg[0][i].snd);
			gx = getCoord(seg[0][i].fst);
			R[1].upd(0, gx, 1);
			R[1].upd(1, gx, seg[0][i].fst);
		}
		ll ans = INF2;
		for (int i = 0; i < Csz - 1; i++)
		{
			for (; j < segSz[1] && seg[1][j].fst <= C[i]; j++)
			{
				int idx = seg[1][j].snd, gx = getCoord(seg[0][idx].snd);
				L[1].upd(0, gx, -1);
				L[1].upd(1, gx, -seg[0][idx].snd);
				L[0].upd(0, gx, 1);
				L[0].upd(1, gx, seg[0][idx].snd);
 
				gx = getCoord(seg[0][idx].fst);
				R[1].upd(0, gx, -1);
				R[1].upd(1, gx, -seg[0][idx].fst);
				R[0].upd(0, gx, 1);
				R[0].upd(1, gx, seg[0][idx].fst);
			}
			
			int idx = solve2(1, 0, INF); opt = eval(1, -1, idx);
			int l = 0, r = idx;
			while (l < r)
			{
				int M = l + ((r - l) >> 1);
				if (eval(1, -1, M) > opt) {l = M + 1;}
				else {r = M;}
			}
			lfm = l;
 
			l = idx, r = INF + 1;
			while (l < r)
			{
				int M = l + ((r - l) >> 1);
				if (eval(1, -1, M) > opt) {r = M;}
				else {l = M + 1;}
			}
			rgm = r - 1;
 
			l = max(0, C[i] - INF), r = C[i] / 2;
			while (r - l > 3)
			{
				int M = l + ((r - l) >> 1);
				if (eval2(M, C[i] - M, min(INF, C[i + 1] - 1 - M)) < eval2(M + 1, C[i] - M - 1, min(INF, C[i + 1] - 2 - M))) {r = M + 1;}
				else {l = M;}
			}
			assert(l <= r);
			int anss = l;
			for (int j = l + 1; j <= r; j++)
			{
				if (eval2(j, C[i] - j, min(INF, C[i + 1] - 1 - j)) < eval2(anss, C[i] - anss, min(INF, C[i + 1] - 1 - anss))) {anss = j;}
			}
			ans = min(ans, eval2(anss, C[i] - anss, min(INF, C[i + 1] - 1 - anss)));
		}
		cout << 2 * ans + res << "\n";
	}
	return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'long long int solve(int, int, int)':
bridge.cpp:61:6: warning: unused variable 'M' [-Wunused-variable]
   61 |  int M;
      |      ^

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