oj.uz

Submission #443596

# Submission time Handle Problem Language Result Execution time Memory
443596 2021-07-11T02:25:52 Z 8e7 Palembang Bridges (APIO15_bridge) C++17
100 / 100
 165 ms 7512 KB 
//Challenge: Accepted
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <utility>
#include <assert.h>
using namespace std;
void debug() {cout << endl;}
template <class T, class ...U> void debug(T a, U ... b) { cout << a << " "; debug(b...);}
template <class T> void pary(T l, T r) {
	while (l != r) {cout << *l << " ";l++;}
	cout << endl;
}
#define ll long long
#define ld long double
#define maxn 100005
#define pii pair<int, int>
#define pdd pair<double, double>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
pii a[maxn], b[maxn];
ll pref[maxn], suf[maxn];
void solve(int n, pii arr[], ll ans[]) {
	ll lc = 0, rc = 0, cur = 0, cost = 0;
	priority_queue<pii, vector<pii>, greater<pii> > pq;
	for (int i = 0;i < n;i++) {
		if (arr[i].ff > cur) pq.push({arr[i].ff, 0}), rc++, cost += arr[i].ff - cur;	
		pq.push({arr[i].ss, 1});
		while (pq.size()) {
			pii seg = pq.top();pq.pop();
			ll dis = seg.ff - cur;
			if (dis == 0 || (lc - rc) * dis < 0) {
				cost += (lc - rc) * dis;
				cur = seg.ff;
				if (seg.ss == 0) rc--;
				else lc++;
			} else {
				pq.push(seg);
				break;
			}
		}
		ans[i] = cost;
	}
}
int main() {
	int k, n;
	cin >> k >> n;
	int cross = 0;
	ll sum = 0;
	int m = 0, ma = 0;
	for (int i = 0;i < n;i++) {
		char p, q;
		int s, t;
		cin >> p >> s >> q >> t;
		if (s > t) swap(s, t);
		sum += t - s;
		ma = max(ma, t);
		if (p != q) {
			a[m++] = {s, t};	
		}
	}
	sort(a, a + m, [&](pii x, pii y) {return x.ff + x.ss < y.ff + y.ss;});
	solve(m, a, pref);
	ll ans = pref[m - 1];
	if (k == 2) {
		for (int i = 0;i < m;i++) {
			b[i] = a[m - 1 - i];
			b[i] = {ma - b[i].ss, ma - b[i].ff};
		}
		solve(m, b, suf);
		ans = min(pref[m - 1], suf[m - 1]);
		for (int i = 0;i < m - 1;i++) {
			ans = min(ans, pref[i] + suf[m - 2 - i]);
		}
	}
	cout << 2 * ans + sum + m << endl;
}
/*
1 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7

2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
   */

Compilation message

bridge.cpp: In function 'int main()':
bridge.cpp:51:6: warning: unused variable 'cross' [-Wunused-variable]
   51 |  int cross = 0;
      |      ^~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 78 ms 2824 KB Output is correct
13 Correct 136 ms 2696 KB Output is correct
14 Correct 115 ms 2620 KB Output is correct
15 Correct 82 ms 1776 KB Output is correct
16 Correct 98 ms 2696 KB Output is correct
17 Correct 126 ms 2716 KB Output is correct
18 Correct 105 ms 2652 KB Output is correct
19 Correct 135 ms 2664 KB Output is correct
20 Correct 109 ms 2716 KB Output is correct
21 Correct 125 ms 2760 KB Output is correct

Subtask #3
9.0 / 9.0

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

Subtask #4
32.0 / 32.0

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

Subtask #5
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 300 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 2 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 2 ms 332 KB Output is correct
21 Correct 2 ms 332 KB Output is correct
22 Correct 2 ms 332 KB Output is correct
23 Correct 2 ms 320 KB Output is correct
24 Correct 2 ms 332 KB Output is correct
25 Correct 90 ms 5928 KB Output is correct
26 Correct 115 ms 6092 KB Output is correct
27 Correct 145 ms 6952 KB Output is correct
28 Correct 164 ms 7512 KB Output is correct
29 Correct 165 ms 7492 KB Output is correct
30 Correct 84 ms 4028 KB Output is correct
31 Correct 120 ms 6776 KB Output is correct
32 Correct 152 ms 7508 KB Output is correct
33 Correct 121 ms 7204 KB Output is correct
34 Correct 156 ms 7460 KB Output is correct
35 Correct 124 ms 6876 KB Output is correct
36 Correct 144 ms 7200 KB Output is correct
37 Correct 60 ms 4160 KB Output is correct