Submission #279759

#	Time	Username	Problem	Language	Result	Execution time	Memory
279759		srvlt	Palembang Bridges (APIO15_bridge)	C++14	0 / 100	19 ms	19232 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;
	if (k == 1) {
		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]);
		}
	}	else {
		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: 0 / 8
• Subtask 2: 0 / 14
• Subtask 3: 0 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37