oj.uz

답안 #764151

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
764151 2023-06-23T07:51:28 Z qwerasdfzxcl Palembang Bridges (APIO15_bridge) C++17
9 / 100
 1 ms 340 KB 
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
constexpr int INF = 1e9;
 
struct DS{
	priority_queue<pair<int, int>> L;
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> R;
 
	int mid, cnt1, cnt0;
	ll sum1, sum0;
 
	void init(){
		while(!L.empty()) L.pop();
		while(!R.empty()) R.pop();
		mid = cnt1 = cnt0 = 0;
		sum1 = sum0 = 0;
	}
 
	void insert(int x, int typ){
		if (x <= mid){
			L.emplace(x, typ);
			if (typ==1) sum1 += x, cnt1++;
		} 
		else{
			R.emplace(x, typ);
			if (typ==0) sum0 += x, cnt0++;
		} 
	}
 
	ll calc(){
		while(L.size() > R.size()){
			if (L.top().second==0) sum0 += L.top().first, cnt0++;
			else sum1 -= L.top().first, cnt1--;
 
			R.push(L.top()); L.pop();
		}
		while(L.size() < R.size()){
			if (R.top().second==0) sum0 -= R.top().first, cnt0--;
			else sum1 += R.top().first, cnt1++;
 
			L.push(R.top()); R.pop();
		}
 
		mid = L.top().first;
		return (ll)mid * (cnt1 - cnt0) - sum1 + sum0;
	}
 
}D;
 
ll solve1(vector<pair<int, int>> V){
	return 0;
}
 
vector<ll> calc(vector<pair<int, int>> V){
	vector<int> X;
	for (auto &[x, y]:V){
		X.push_back(x); X.push_back(y);
		if (x > y) swap(x, y);
	}
 
	sort(V.begin(), V.end(), [](const pair<int, int> &x, const pair<int, int> &y){return x.first + x.second < y.first + y.second;});
	
	vector<ll> ret = {0};
	D.init();
 
	for (int i=0;i<(int)V.size();i++){
		D.insert(V[i].first, 0);
		D.insert(V[i].second, 1);
 
		ret.push_back(D.calc());
	}
 
	return ret;
}
 
ll solve2(vector<pair<int, int>> V){
	ll ret = 4e18, lenS = 0;
	for (auto &[x, y]:V) lenS += abs(x-y);
 
 	auto V0 = V;
	auto L = calc(V);
	for (auto &[x, y]:V) x = INF-x, y = INF-y;
	auto R = calc(V);
 
	reverse(R.begin(), R.end());
	for (int i=0;i<(int)L.size();i++) if (i==0 || V0[i-1].first + V0[i-1].second != V0[i].first + V0[i].second){
		ret = min(ret, L[i] + R[i]);
	}
 
	return ret * 2 + lenS;
}
 
int main(){
	int k, n;
	scanf("%d %d", &k, &n);
 
	ll ans = 0;
	vector<pair<int, int>> V;
 
	for (int i=1;i<=n;i++){
		char cx, cy;
		int px, py;
		scanf(" %c %d %c %d", &cx, &px, &cy, &py);
 
		if (cx==cy) {ans += abs(px-py); continue;}
		if (cx=='B') swap(px, py);
		V.emplace_back(px, py);
 
		ans++;
	}

	if (k==2) ans += solve2(V);
	else ans += solve1(V);
	printf("%lld\n", ans);
}

Compilation message

bridge.cpp: In function 'int main()':
bridge.cpp:97:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |  scanf("%d %d", &k, &n);
      |  ~~~~~^~~~~~~~~~~~~~~~~
bridge.cpp:105:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |   scanf(" %c %d %c %d", &cx, &px, &cy, &py);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

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

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Incorrect 1 ms 340 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Incorrect 1 ms 340 KB Output isn't correct
15 Halted 0 ms 0 KB -