oj.uz

Submission #332409

# Submission time Handle Problem Language Result Execution time Memory
332409 2020-12-02T09:54:59 Z syy Palembang Bridges (APIO15_bridge) C++17
100 / 100
 107 ms 11116 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define FOR(i, a, b) for(ll i = (ll)a; i <= (ll)b; i++)
#define DEC(i, a, b) for(ll i = (ll)a; i >= (ll)b; i--)
typedef pair<ll, ll> pi;
typedef pair<pi, ll> pii;
typedef pair<ll, pi> ipi;
typedef pair<pi, pi> pipi;
#define f first
#define s second
typedef vector<ll> vi;
typedef vector<pi> vpi;
typedef vector<pii> vpii;
#define pb push_back
#define pf push_front
#define all(v) v.begin(), v.end()
#define size(v) (ll) v.size()
#define disc(v) sort(all(v)); v.resize(unique(all(v)) - v.begin());
#define INF (ll) 1e9 + 100
#define LLINF (ll) 1e18
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define sandybridge __attribute__((optimize("Ofast"), target("arch=sandybridge")))
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
inline ll rand(ll x, ll y) { ++y; return (rng() % (y-x)) + x; } //inclusivesss

struct seg {
	ll a, b, mid;
	seg (ll x, ll y) {
		a = x, b = y, mid = (a+b)/2;
	}
	bool operator<(seg x) const {
		return mid < x.mid;
	}	
};

ll k, n, m, a, b, ans, val[2][100005], lsum, rsum;
char x, y;
vector<seg> v;
vi coord;
priority_queue<ll> L;
priority_queue<ll, vi, greater<ll>> R;

int main() {
	fastio; cin >> k >> n;
	ans = n;
	FOR(i, 1, n) {
		cin >> x >> a >> y >> b;
		if (x == y) ans += abs(b-a) - 1;
		else {
			v.pb(seg(a, b));
			coord.pb(a);
			coord.pb(b);
		}
	}
	if (v.empty()) {
		cout << ans;
		return 0;
	}
	m = size(v);
	v.pb(seg(-1, -1));
	sort(all(v));
	v.pb(seg(-1, -1));
	if (k == 1) {
		sort(all(coord));
		ll x = coord[size(coord)/2];
		for (auto it:coord) ans += abs(it - x);
		cout << ans;
		return 0;
	}
	FOR(temp, 0, 1) {
		while (!L.empty()) L.pop();
		while (!R.empty()) R.pop();
		lsum = rsum = 0;
		FOR(i, 1, m) {
			a = v[i].a, b = v[i].b;
			if (L.empty()) {
				L.push(min(a, b)), R.push(max(a, b));
				lsum += min(a, b), rsum += max(a, b);
			} else {
				ll med = L.top();
				if (a <= med) L.push(a), lsum += a;
				else R.push(a), rsum += a;
				if (b <= med) L.push(b), lsum += b;
				else R.push(b), rsum += b;
			}
			while (size(R) < size(L)) {
				rsum += L.top();
				lsum -= L.top();
				R.push(L.top());
				L.pop();
			}
			while (size(L) < size(R)) {
				lsum += R.top();
				rsum -= R.top();
				L.push(R.top());
				R.pop();
			}
			assert(size(R) == size(L));
			ll med = L.top();
			val[temp][i] = med * size(L) - lsum + rsum - med * size(R);
		}
		reverse(all(v));
	}
	ll ans2 = LLINF;
	FOR(i, 0, m) ans2 = min(ans2, val[0][i] + val[1][m-i]);
	cout << ans + ans2;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 36 ms 5492 KB Output is correct
13 Correct 58 ms 6764 KB Output is correct
14 Correct 45 ms 5748 KB Output is correct
15 Correct 33 ms 4212 KB Output is correct
16 Correct 37 ms 6124 KB Output is correct
17 Correct 54 ms 6784 KB Output is correct
18 Correct 47 ms 6380 KB Output is correct
19 Correct 57 ms 6764 KB Output is correct
20 Correct 39 ms 6400 KB Output is correct
21 Correct 52 ms 6508 KB Output is correct

Subtask #3
9.0 / 9.0

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

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 492 KB Output is correct
14 Correct 1 ms 492 KB Output is correct
15 Correct 1 ms 492 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 2 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 492 KB Output is correct
20 Correct 2 ms 492 KB Output is correct
21 Correct 2 ms 492 KB Output is correct
22 Correct 1 ms 492 KB Output is correct
23 Correct 1 ms 492 KB Output is correct
24 Correct 1 ms 492 KB Output is correct

Subtask #5
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 492 KB Output is correct
14 Correct 1 ms 492 KB Output is correct
15 Correct 2 ms 492 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 2 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 492 KB Output is correct
20 Correct 1 ms 492 KB Output is correct
21 Correct 1 ms 492 KB Output is correct
22 Correct 1 ms 492 KB Output is correct
23 Correct 1 ms 492 KB Output is correct
24 Correct 1 ms 492 KB Output is correct
25 Correct 48 ms 9968 KB Output is correct
26 Correct 69 ms 9708 KB Output is correct
27 Correct 90 ms 10604 KB Output is correct
28 Correct 96 ms 11116 KB Output is correct
29 Correct 107 ms 10732 KB Output is correct
30 Correct 50 ms 5772 KB Output is correct
31 Correct 48 ms 10860 KB Output is correct
32 Correct 84 ms 11116 KB Output is correct
33 Correct 64 ms 11116 KB Output is correct
34 Correct 90 ms 11116 KB Output is correct
35 Correct 60 ms 10604 KB Output is correct
36 Correct 83 ms 10860 KB Output is correct
37 Correct 45 ms 9580 KB Output is correct