oj.uz

Submission #39525

# Submission time Handle Problem Language Result Execution time Memory
39525 2018-01-16T09:21:16 Z qoo2p5 Palembang Bridges (APIO15_bridge) C++14
63 / 100
 2000 ms 167052 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = (int) 1e9 + 123;
const ll LINF = (ll) 1e18 + 123;

#define rep(i, s, t) for (auto i = (s); i < (t); ++(i))
#define per(i, s, t) for (auto i = (s); i >= (t); --(i))
#define sz(x) ((int) (x).size())
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()

bool mini(auto &x, const auto &y) {
	if (y < x) {
		x = y;
		return 1;
	}
	return 0;
}

bool maxi(auto &x, const auto &y) {
	if (y < x) {
		x = y;
		return 1;
	}
	return 0;
}

void run();

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	run();
	return 0;
}

const int N = (int) 1e5 + 123;

struct Fenwick {
	unordered_map<int, ll> f;
	
	Fenwick() {
		f.reserve(4 * N * 20);
		f.max_load_factor(0.25);
	}
	
	void add(int x, ll y) {
		x++;
		for (; x < INF; x += x & (-x)) {
			f[x] += y;
		}
	}
	
	ll get(int r) {
		ll res = 0;
		r++;
		for (; r > 0; r -= r & (-r)) {
			if (f.count(r)) res += f[r];
		}
		return res;
	}
	
	void clear() {
		for (auto &it : f) it.second = 0;
	}
};

int k, n;
vector<pair<ll, ll>> a;
vector<ll> cool;
ll total;
ll pref[N], suff[N];

void solve1() {
	vector<ll> p;
	{
		for (auto &it : a) {
			p.pb(it.first);
			p.pb(it.second);
		}
		sort(all(p));
	}
	
	int k = sz(p) / 2;
	ll x = p[k];
	ll ans = 0;
	for (ll y : p) ans += abs(x - y);
	
	ans += total;
	cout << ans << "\n";
}

ll solve() {
	sort(all(a), [] (const pair<ll, ll> &x, const pair<ll, ll> &y) {
		return x.first + x.second < y.first + y.second;
	});
	
	Fenwick f_sum, f_cnt;
	
	{
		f_sum.clear();
		f_cnt.clear();
		multiset<ll> p, q;
		ll sum = 0;
		ll cnt = 0;
		rep(i, 0, n) {
			f_sum.add(a[i].first, a[i].first);
			f_cnt.add(a[i].first, 1);
			f_sum.add(a[i].second, a[i].second);
			f_cnt.add(a[i].second, 1);
			sum += a[i].first + a[i].second;
			cnt += 2;
			
			q.insert(a[i].first);
			q.insert(a[i].second);
			while (sz(q) > i + 1) {
				ll el = *q.rbegin();
				q.erase(q.find(el));
				p.insert(el);
			}
			assert(sz(q) == sz(p));
			while (*q.rbegin() > *p.begin()) {
				ll x = *q.rbegin();
				ll y = *p.begin();
				q.erase(q.find(x));
				q.insert(y);
				p.erase(p.find(y));
				p.insert(x);
			}
			ll mid = *q.rbegin();
			ll sum_l = f_sum.get(mid);
			ll sum_r = sum - sum_l;
			ll cnt_l = f_cnt.get(mid);
			ll cnt_r = cnt - cnt_l;
			pref[i] = (mid * cnt_l - sum_l) + (sum_r - mid * cnt_r);
		}
	}
	
	{
		f_sum.clear();
		f_cnt.clear();
		multiset<ll> p, q;
		ll sum = 0;
		ll cnt = 0;
		per(i, n - 1, 0) {
			f_sum.add(a[i].first, a[i].first);
			f_cnt.add(a[i].first, 1);
			f_sum.add(a[i].second, a[i].second);
			f_cnt.add(a[i].second, 1);
			sum += a[i].first + a[i].second;
			cnt += 2;
			
			q.insert(a[i].first);
			q.insert(a[i].second);
			while (sz(q) > n - i) {
				ll el = *q.rbegin();
				q.erase(q.find(el));
				p.insert(el);
			}
			assert(sz(q) == sz(p));
			while (*q.rbegin() > *p.begin()) {
				ll x = *q.rbegin();
				ll y = *p.begin();
				q.erase(q.find(x));
				q.insert(y);
				p.erase(p.find(y));
				p.insert(x);
			}
			ll mid = *q.rbegin();
			ll sum_l = f_sum.get(mid);
			ll sum_r = sum - sum_l;
			ll cnt_l = f_cnt.get(mid);
			ll cnt_r = cnt - cnt_l;
			suff[i] = (mid * cnt_l - sum_l) + (sum_r - mid * cnt_r);
		}
	}
	
	ll ans = suff[0];
	rep(i, 0, n) {
		mini(ans, pref[i] + suff[i + 1]);
	}
	return ans;
}

void run() {
	cin >> k >> n;
	rep(i, 0, n) {
		char t1, t2;
		ll x1, x2;
		cin >> t1 >> x1 >> t2 >> x2;
		if (t1 == t2) {
			total += abs(x1 - x2);
		} else {
			if (x1 > x2) {
				swap(t1, t2);
				swap(x1, x2);
			}
			a.pb({x1, x2});
			cool.pb(x1);
			cool.pb(x2);
		}
	}
	sort(all(cool));
	cool.resize(unique(all(cool)) - cool.begin());
	sort(all(a));
	n = sz(a);
	total += n;
	if (k == 1) {
		solve1();
		return;
	}
	if (n == 0) {
		cout << total << "\n";
		return;
	}
	
	ll ans = solve();
	
	ans += total;
	cout << ans << "\n";
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3760 KB Output is correct
2 Correct 0 ms 3760 KB Output is correct
3 Correct 0 ms 3760 KB Output is correct
4 Correct 0 ms 3760 KB Output is correct
5 Correct 0 ms 3760 KB Output is correct
6 Correct 0 ms 3760 KB Output is correct
7 Correct 0 ms 3760 KB Output is correct
8 Correct 0 ms 3760 KB Output is correct
9 Correct 0 ms 3760 KB Output is correct
10 Correct 0 ms 3760 KB Output is correct
11 Correct 0 ms 3760 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3760 KB Output is correct
2 Correct 0 ms 3760 KB Output is correct
3 Correct 0 ms 3760 KB Output is correct
4 Correct 0 ms 3760 KB Output is correct
5 Correct 0 ms 3760 KB Output is correct
6 Correct 0 ms 3760 KB Output is correct
7 Correct 0 ms 3760 KB Output is correct
8 Correct 0 ms 3760 KB Output is correct
9 Correct 0 ms 3760 KB Output is correct
10 Correct 0 ms 3760 KB Output is correct
11 Correct 0 ms 3760 KB Output is correct
12 Correct 33 ms 11996 KB Output is correct
13 Correct 89 ms 11996 KB Output is correct
14 Correct 53 ms 11996 KB Output is correct
15 Correct 46 ms 7900 KB Output is correct
16 Correct 36 ms 11996 KB Output is correct
17 Correct 36 ms 11996 KB Output is correct
18 Correct 53 ms 11996 KB Output is correct
19 Correct 49 ms 11996 KB Output is correct
20 Correct 36 ms 11996 KB Output is correct
21 Correct 63 ms 11996 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3760 KB Output is correct
2 Correct 0 ms 3760 KB Output is correct
3 Correct 43 ms 131504 KB Output is correct
4 Correct 43 ms 131636 KB Output is correct
5 Correct 36 ms 131504 KB Output is correct
6 Correct 46 ms 131504 KB Output is correct
7 Correct 46 ms 131504 KB Output is correct
8 Correct 43 ms 131636 KB Output is correct
9 Correct 46 ms 131504 KB Output is correct
10 Correct 49 ms 131636 KB Output is correct
11 Correct 56 ms 131504 KB Output is correct
12 Correct 56 ms 131504 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3760 KB Output is correct
2 Correct 0 ms 3760 KB Output is correct
3 Correct 46 ms 131504 KB Output is correct
4 Correct 49 ms 131636 KB Output is correct
5 Correct 49 ms 131504 KB Output is correct
6 Correct 56 ms 131504 KB Output is correct
7 Correct 46 ms 131504 KB Output is correct
8 Correct 53 ms 131636 KB Output is correct
9 Correct 46 ms 131504 KB Output is correct
10 Correct 59 ms 131636 KB Output is correct
11 Correct 43 ms 131504 KB Output is correct
12 Correct 49 ms 131504 KB Output is correct
13 Correct 43 ms 131636 KB Output is correct
14 Correct 56 ms 131636 KB Output is correct
15 Correct 86 ms 132824 KB Output is correct
16 Correct 36 ms 131504 KB Output is correct
17 Correct 53 ms 131504 KB Output is correct
18 Correct 59 ms 131768 KB Output is correct
19 Correct 49 ms 131636 KB Output is correct
20 Correct 73 ms 132956 KB Output is correct
21 Correct 49 ms 131768 KB Output is correct
22 Correct 63 ms 132428 KB Output is correct
23 Correct 53 ms 131636 KB Output is correct
24 Correct 53 ms 131768 KB Output is correct

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3760 KB Output is correct
2 Correct 0 ms 3760 KB Output is correct
3 Correct 53 ms 131504 KB Output is correct
4 Correct 49 ms 131636 KB Output is correct
5 Correct 36 ms 131504 KB Output is correct
6 Correct 43 ms 131504 KB Output is correct
7 Correct 39 ms 131504 KB Output is correct
8 Correct 33 ms 131636 KB Output is correct
9 Correct 49 ms 131504 KB Output is correct
10 Correct 43 ms 131636 KB Output is correct
11 Correct 53 ms 131504 KB Output is correct
12 Correct 53 ms 131504 KB Output is correct
13 Correct 43 ms 131636 KB Output is correct
14 Correct 39 ms 131636 KB Output is correct
15 Correct 66 ms 132824 KB Output is correct
16 Correct 46 ms 131504 KB Output is correct
17 Correct 43 ms 131504 KB Output is correct
18 Correct 49 ms 131768 KB Output is correct
19 Correct 46 ms 131636 KB Output is correct
20 Correct 63 ms 132956 KB Output is correct
21 Correct 56 ms 131768 KB Output is correct
22 Correct 53 ms 132428 KB Output is correct
23 Correct 59 ms 131636 KB Output is correct
24 Correct 36 ms 131768 KB Output is correct
25 Correct 736 ms 145008 KB Output is correct
26 Correct 789 ms 145008 KB Output is correct
27 Execution timed out 2000 ms 167052 KB Execution timed out
28 Halted 0 ms 0 KB -