Submission #668008

#	Time	Username	Problem	Language	Result	Execution time	Memory
668008		chanhchuong123	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	82 ms	5744 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
#define task "C"
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
  	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
  	if (a < b) {a = b; return true;} return false;
}

const int N = 1e5 + 4;
int n, k;
long long sameSide;
vector<pair<int, int>> a;

void solve1() {
	vector<int> v;
	for (int i = 0; i < a.size(); i++) {
		v.push_back(a[i].fi);
		v.push_back(a[i].se);
	}
	sort(all(v));
	long long sum = 0;
	int median = v[v.size() / 2];
	for (int i = 0; i < a.size(); i++) {
		sum += abs(a[i].fi - median);
		sum += abs(a[i].se - median);
	}
	cout << sum + sameSide + a.size();
}


long long lsum, rsum, pre[N]; priority_queue<int> pql;
priority_queue<int, vector<int>, greater<int>> pqr;

void insert(int x) {
	int median = pql.size() ? pql.top() : 1000000001;
	if (x <= median) {
		pql.push(x);
		lsum += x;
	} else {
		pqr.push(x);
		rsum += x;
	}

	if (pqr.size() + 1 < pql.size()) {
		int change = pql.top();
		pql.pop();
		pqr.push(change);
		lsum -= change;
		rsum += change;
	} else if (pql.size() < pqr.size()) {
		int change = pqr.top();
		pqr.pop();
		pql.push(change);
		lsum += change;
		rsum -= change;
	}
}

void solve2() {
	sort(all(a), [](pair<int, int> &u, pair<int, int> &v) {
		return u.fi + u.se < v.fi + v.se;
	});

	for (int i = 0; i < a.size(); i++) {
		insert(a[i].fi); 
		insert(a[i].se);
		pre[i] = rsum - lsum;
	}

	while (pql.size()) pql.pop();
	while (pqr.size()) pqr.pop();
	lsum = 0; rsum = 0;

	long long ans = pre[a.size() - 1];
	for (int i = a.size() - 1; i > 0; i--) {
		insert(a[i].fi); insert(a[i].se);
		mini(ans, pre[i - 1] + rsum - lsum);
	}
	cout << ans + sameSide + a.size();
}

int main() {
 	ios_base::sync_with_stdio(0);
  	cin.tie(0); cout.tie(0);

  	if (fopen(task".inp","r")) {
  		freopen(task".inp","r",stdin);
   		freopen(task".out","w",stdout);
 	}

 	cin >> k >> n;
 	for (int i = 1; i <= n; i++) {
 		char P, Q; int S, T;
 		cin >> P >> S >> Q >> T;
 		if (P == Q) sameSide += abs(S - T);
 		else a.push_back(make_pair(S, T));
 	}
 	if (k == 1) solve1();
 	else solve2();
}

Compilation message (stderr)

bridge.cpp: In function 'void solve1()':
bridge.cpp:23:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |  for (int i = 0; i < a.size(); i++) {
      |                  ~~^~~~~~~~~~
bridge.cpp:30:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |  for (int i = 0; i < a.size(); i++) {
      |                  ~~^~~~~~~~~~
bridge.cpp: In function 'void solve2()':
bridge.cpp:71:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |  for (int i = 0; i < a.size(); i++) {
      |                  ~~^~~~~~~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:94:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |     freopen(task".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:95:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |      freopen(task".out","w",stdout);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 32 / 32
• Subtask 5: 37 / 37