답안 #336179

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
336179	2020-12-15T00:44:07 Z	super_j6	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	161 ms	7132 KB

bridge

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<int, int>
#define f first
#define s second

const int mxn = 100000;
int n, m, k;
pi a[mxn];
ll f[2][mxn];
vector<int> v;

ll sl[2], sr[2];
priority_queue<int> l, ql[2];
priority_queue<int, vector<int>, greater<int>> r, qr[2];

void add(int x, int y){
	if(l.empty() || x <= l.top()) l.push(x);
	else r.push(x);
	while(l.size() < r.size()) l.push(r.top()), r.pop();
	while(r.size() + 1 < l.size()) r.push(l.top()), l.pop();
	
	if(x <= l.top()) ql[y].push(x), sl[y] += x;
	else qr[y].push(x), sr[y] += x;
	for(int t = 0; t < 2; t++){
		while(!ql[t].empty() && ql[t].top() > l.top()){
			sl[t] -= ql[t].top();
			sr[t] += ql[t].top();
			qr[t].push(ql[t].top());
			ql[t].pop();
		}
		while(!qr[t].empty() && qr[t].top() <= l.top()){
			sr[t] -= qr[t].top();
			sl[t] += qr[t].top();
			ql[t].push(qr[t].top());
			qr[t].pop();
		}
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> k >> n;
	
	ll s = 0;
	for(int i = 0; i < n; i++){
		char c, d;
		int x, y;
		cin >> c >> x >> d >> y;
		if(x > y) swap(x, y);
		s += y - x;
		if(c != d) s++, a[m++] = {x, y};
	}
	
	sort(a, a + m, [&](pi x, pi y){
		return x.f + x.s < y.f + y.s;
	});
	
	for(int t = 0; t < 2; t++){
		while(!l.empty()) l.pop();
		while(!r.empty()) r.pop();
		for(int i = 0; i < 2; i++){
			sl[i] = sr[i] = 0;
			while(!ql[i].empty()) ql[i].pop();
			while(!qr[i].empty()) qr[i].pop();
		}
		for(int i = 0; i < m; i++){
			add(a[i].f, 0), add(a[i].s, 1);
			f[t][i] += sr[0] - (ll)l.top() * qr[0].size();
			f[t][i] += (ll)l.top() * ql[1].size() - sl[1];
		}
		reverse(a, a + m);
	}
	reverse(f[1], f[1] + m);
	
	ll ret = !!m * 0x3f3f3f3f3f3f3f3f;
	if(k & 1) ret = f[1][0];
	else for(int i = 1; i < m; i++) ret = min(ret, f[0][i - 1] + f[1][i]);
	ret = 2 * ret + s;
	
	cout << ret << endl;

	return 0;
}

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	512 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	2 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	384 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	2 ms	364 KB	Output is correct

Subtask #2
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 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	2 ms	364 KB	Output is correct
5	Correct	2 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	2 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	2 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	2 ms	364 KB	Output is correct
12	Correct	58 ms	5004 KB	Output is correct
13	Correct	161 ms	4456 KB	Output is correct
14	Correct	114 ms	4156 KB	Output is correct
15	Correct	80 ms	2868 KB	Output is correct
16	Correct	52 ms	4436 KB	Output is correct
17	Correct	114 ms	4888 KB	Output is correct
18	Correct	78 ms	4440 KB	Output is correct
19	Correct	128 ms	4828 KB	Output is correct
20	Correct	70 ms	4564 KB	Output is correct
21	Correct	118 ms	4956 KB	Output is correct

Subtask #3
9.0 / 9.0

#	결과	실행 시간	메모리	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	384 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

#	결과	실행 시간	메모리	Grader output
1	Correct	0 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	384 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	364 KB	Output is correct
14	Correct	2 ms	364 KB	Output is correct
15	Correct	2 ms	364 KB	Output is correct
16	Correct	1 ms	364 KB	Output is correct
17	Correct	1 ms	364 KB	Output is correct
18	Correct	1 ms	364 KB	Output is correct
19	Correct	2 ms	364 KB	Output is correct
20	Correct	2 ms	364 KB	Output is correct
21	Correct	1 ms	364 KB	Output is correct
22	Correct	2 ms	364 KB	Output is correct
23	Correct	1 ms	364 KB	Output is correct
24	Correct	1 ms	364 KB	Output is correct

Subtask #5
37.0 / 37.0

#	결과	실행 시간	메모리	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	364 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	2 ms	364 KB	Output is correct
16	Correct	1 ms	364 KB	Output is correct
17	Correct	1 ms	364 KB	Output is correct
18	Correct	1 ms	364 KB	Output is correct
19	Correct	1 ms	364 KB	Output is correct
20	Correct	1 ms	364 KB	Output is correct
21	Correct	1 ms	364 KB	Output is correct
22	Correct	1 ms	364 KB	Output is correct
23	Correct	2 ms	364 KB	Output is correct
24	Correct	1 ms	364 KB	Output is correct
25	Correct	58 ms	5012 KB	Output is correct
26	Correct	105 ms	5440 KB	Output is correct
27	Correct	150 ms	6120 KB	Output is correct
28	Correct	136 ms	6692 KB	Output is correct
29	Correct	136 ms	6692 KB	Output is correct
30	Correct	69 ms	3832 KB	Output is correct
31	Correct	69 ms	6100 KB	Output is correct
32	Correct	122 ms	7132 KB	Output is correct
33	Correct	77 ms	6360 KB	Output is correct
34	Correct	119 ms	7132 KB	Output is correct
35	Correct	71 ms	6484 KB	Output is correct
36	Correct	119 ms	6948 KB	Output is correct
37	Correct	64 ms	5204 KB	Output is correct

답안 #336179

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 14.0 / 14.0

Subtask #3 9.0 / 9.0

Subtask #4 32.0 / 32.0

Subtask #5 37.0 / 37.0

Subtask #1
8.0 / 8.0

Subtask #2
14.0 / 14.0

Subtask #3
9.0 / 9.0

Subtask #4
32.0 / 32.0

Subtask #5
37.0 / 37.0