Submission #279763

#	Time	Username	Problem	Language	Result	Execution time	Memory
279763		srvlt	Palembang Bridges (APIO15_bridge)	C++14	63 / 100	2053 ms	30196 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define all(x) begin(x), end(x)
#define SZ(x) (int)(x).size()
#define cps(x) sort(all(x)), (x).erase(unique(all(x)), end(x))
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int n0 = 1e5 + 123, m0 = 4e5 + 123;
int n, k, m, l[n0], r[n0], l0[n0], r0[n0];
ll ans, pref[n0], suf[n0];
vector <int> mr[m0], ml[m0];

int M;
ll q[2][m0], val[2][m0], Q[2], VAL[2];
void upd(int c, int x, ll y) {
	Q[c]++, VAL[c] += y;
	for (; x < M; x |= (x + 1)) {
		val[c][x] += y;
		q[c][x]++;
	}
}

ll getsum(int c, int x) {
	ll res = 0;
	for (; x >= 0; x = (x & (x + 1)) - 1)
		res += val[c][x];
	return res;
}

ll getnum(int c, int x) {
	ll res = 0;
	for (; x >= 0; x = (x & (x + 1)) - 1)
		res += q[c][x];
	return res;
}

void clean() {
	Q[0] = Q[1] = VAL[0] = VAL[1] = 0;
	for (int i = 0; i < M; i++)
		val[0][i] = val[1][i] = q[0][i] = q[1][i] = 0;
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	cin >> k >> n;
	for (int i = 0; i < n; i++) {
		char c1, c2;
		int L, R;
		cin >> c1 >> L >> c2 >> R;
		if (L > R) swap(L, R);
		ans += R - L;
		if (c1 != c2) {
			l[m] = L, r[m] = R;
			m++;
		}
	}
	vector <int> v;
	for (int i = 0; i < m; i++)
		v.pb(l[i]), v.pb(r[i]);
	sort(all(v));
	ll ans2 = ans;
	int j = SZ(v) / 2;
	for (int i = 0; i < m; i++) {
		if (v[j] < l[i]) ans2 += 2 * (l[i] - v[j]);
		if (r[i] < v[j]) ans2 += 2 * (v[j] - r[i]);
	}
	if (k == 1) return cout << ans2 + m, 0;
	v.erase(unique(all(v)), end(v));
	vector <int> vec;
	for (int i = 0; i < m; i++) {
		l0[i] = lower_bound(all(v), l[i]) - v.begin();
		r0[i] = lower_bound(all(v), r[i]) - v.begin();
		vec.pb(l[i] + r[i]);
		ml[l0[i]].pb(i), mr[r0[i]].pb(i);
	}
	cps(vec);
	ll num = 0, cur = 0;
	for (int i = 0; i < SZ(v); i++) {
		if (i)
			cur += (v[i] - v[i - 1]) * num;
		pref[i] = cur;
		num += SZ(mr[i]);
	}
	num = 0, cur = 0;
	for (int i = SZ(v) - 1; i >= 0; i--) {
		if (i < SZ(v) - 1)
			cur += (v[i + 1] - v[i]) * num;
		suf[i] = cur;
		num += SZ(ml[i]);
	}
	ll can = 1e18;
	M = SZ(vec);
	
	vector <array <int, 2>> seg;
	for (int i = 0; i < SZ(v); i++) {
		//clean();
		seg.clear();
		for (int j = i + 1; j < SZ(v); j++) {
			for (int k : mr[j]) {
				int L = l[k], R = r[k];
				if (L < v[i]) continue;
				//int pos = lower_bound(all(vec), L + R) - vec.begin();
				//upd(0, pos, L);
				//upd(1, pos, R);
				seg.pb({L, R});
			}
			//int pos2 = upper_bound(all(vec), v[i] + v[j]) - vec.begin() - 1;
			//ll tmp = getsum(0, pos2) - getnum(0, pos2) * v[i];
			//ll tmp2 = getnum(1, pos2) * v[j] - getsum(1, pos2);
			//tmp2 = (Q[1] * v[j] - VAL[1]) - tmp2;
			//can = min(can, pref[i] + suf[j] + tmp + tmp2);
			ll tmp = 0;
			for (auto k : seg)
				tmp += min(k[0] - v[i], v[j] - k[1]);
			can = min(can, pref[i] + suf[j] + tmp);
		}
	}
	ans += can * 2;
	cout << min(ans, ans2) + m;
}

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