Submission #114333

#	Time	Username	Problem	Language	Result	Execution time	Memory
114333		Bruteforceman	Palembang Bridges (APIO15_bridge)	C++11	100 / 100	337 ms	23912 KiB

bridge

#include "bits/stdc++.h"
using namespace std;
typedef pair <int, int> pii;

vector <pii> v;
long long pre[1000010], suf[1000010];

bool cmp(pii a, pii b) {
	return a.first + a.second < b.first + b.second;
}

long long solver(vector <pii> u) {
	vector <int> a;
	for(auto i : u) {
		a.push_back(i.first);
		a.push_back(i.second);
	}
	sort(a.begin(), a.end());
	long long ans = 0;
	for(int i : a) {
		ans += abs(a[a.size() / 2] - i);
	}
	return ans;
}

struct median_ds {
	multiset <int> P, Q;
	long long sumP, sumQ;
	median_ds () {
		sumP = sumQ = 0;
	}
	void add(int x) {
		if(P.empty()) {
			P.insert(x);
			sumP += x;
		} else if (*P.rbegin() < x) {
			Q.insert(x);
			sumQ += x;
		} else {
			P.insert(x);
			sumP += x;
		}
		if(P.size() < Q.size()) {
			sumQ -= *Q.begin();
			sumP += *Q.begin();
			P.insert(*Q.begin());
			Q.erase(Q.begin());
		}
		if(P.size() > Q.size() + 1) {
			sumP -= *P.rbegin();
			sumQ += *P.rbegin();
			Q.insert(*P.rbegin());
			P.erase(P.find(*P.rbegin()));
		}
	}
	long long getCost() {
		long long med = *P.rbegin();
		long long ans = sumQ - sumP;
		ans += med * P.size();
		ans -= med * Q.size();
		return ans;
	}
} S, T; 

int main(int argc, char const *argv[])
{
	int k, n;
	scanf("%d %d", &k, &n);
	
	long long add = 0;
	for(int i = 1; i <= n; i++) {
		char p, q;
		int s, t;
		scanf(" %c %d %c %d", &p, &s, &q, &t);
		if(p == q) {
			add += abs(s - t);
		} else {
			add += 1;
			if(s > t) swap(s, t);
			v.push_back(pii(s, t));
		}
	}
	if(v.size() == 0) {
		printf("%lld\n", add);
		exit(0);
	}
	sort(v.begin(), v.end(), cmp);
	for(int i = 0; i < v.size(); i++) {
		S.add(v[i].first);
		S.add(v[i].second);
		pre[i] = S.getCost();
	}
	for(int i = v.size() - 1; i >= 0; i--) {
		T.add(v[i].first);
		T.add(v[i].second);
		suf[i] = T.getCost();
	}
	
	long long ans = LLONG_MAX;
	if(k == 2) {
		for(int i = 0; i < v.size(); i++) {
			ans = min(ans, pre[i] + suf[i + 1]);
		}
	} else {
		ans = pre[v.size() - 1];
	}
	printf("%lld\n", ans + add);
	return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'int main(int, const char**)':
bridge.cpp:88:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < v.size(); i++) {
                 ~~^~~~~~~~~~
bridge.cpp:101:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < v.size(); i++) {
                  ~~^~~~~~~~~~
bridge.cpp:68:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &k, &n);
  ~~~~~^~~~~~~~~~~~~~~~~
bridge.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c %d %c %d", &p, &s, &q, &t);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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