제출 #47183

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
47183		szawinis	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	945 ms	68580 KiB

bridge

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

vector<pair<ll, ll> > f;
void update(int i, ll v) {
	++i;
	while(i < f.size()) {
		f[i].first += v;
		++f[i].second;
		i += i & -i;
	}
}
pair<ll, ll> query(int l, int r) {
	pair<ll, ll> ret = {0, 0};
	if(l > r) return ret;
	for(int i = r+1; i > 0; i -= i & -i)
		ret.first += f[i].first, ret.second += f[i].second;
	for(int i = l; i > 0; i -= i & -i)
		ret.first -= f[i].first, ret.second -= f[i].second;
	return ret;
}

int k, n;
ll ans;
vector<pair<int, int> > a;
vector<int> vals, sums;
unordered_map<int, int> mp;

vector<ll> solve(function<bool(int,int)> comp) { // comparator
	vector<ll> res;
	ordered_set<pair<int,int> > oset;
	res.resize(sums.size());
	f.assign(vals.size() + 1, make_pair(0, 0));

	for(int i = 0, j = 0; i < sums.size(); i++) {
		while(j < a.size() && comp(a[j].first + a[j].second, sums[i])) {
			oset.insert(make_pair(a[j].first, j << 1));
			oset.insert(make_pair(a[j].second, j << 1 | 1));
			update(mp[a[j].first], a[j].first);
			update(mp[a[j].second], a[j].second);
			++j;
		}
		int place_first = mp[oset.find_by_order(oset.size() >> 1)->first];
		ll sum, cnt;
		tie(sum, cnt) = query(place_first, vals.size()-1);
		res[i] += sum - cnt * vals[place_first];
		tie(sum, cnt) = query(0, place_first);
		res[i] += cnt * vals[place_first] - sum;
	}
	return res;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> k >> n;
	for(int i = 0; i < n; i++) {
		char P, Q; int s, t;
		cin >> P >> s >> Q >> t;
		if(P == Q) ans += abs(s-t);
		else {
			a.emplace_back(s, t);
			vals.push_back(s);
			vals.push_back(t);
			sums.push_back(s+t);
		}
	}
	ans += a.size();

	if(a.empty()) {
		cout << ans;
		return 0;
	}

	sort(a.begin(), a.end(), [] (auto x, auto y) { return x.first + x.second < y.first + y.second; });
	sort(sums.begin(), sums.end());
	sums.resize(unique(sums.begin(), sums.end()) - sums.begin());
	sort(vals.begin(), vals.end());
	vals.resize(unique(vals.begin(), vals.end()) - vals.begin());
	for(int i = 0; i < vals.size(); i++) mp[vals[i]] = i;

	vector<ll> res1 = solve(less_equal<int>());
	if(k == 1) {
		ans += res1[sums.size()-1];
		cout << ans;
		return 0;
	}
	reverse(a.begin(), a.end());
	reverse(sums.begin(), sums.end());
	vector<ll> res2 = solve(greater<int>());
	vector<ll> res = vector<ll>(sums.size());
	for(int i = 0; i < sums.size(); i++) res[i] = res1[i] + res2[sums.size()-1-i];

	// for(ll x: res1) cout << x << ' ';
	// cout << endl;
	// for(ll x: res2) cout << x << ' ';
	// cout << endl;

	ans += *min_element(res.begin(), res.end());
	cout << ans;
}

컴파일 시 표준 에러 (stderr) 메시지

bridge.cpp: In function 'void update(int, ll)':
bridge.cpp:13:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(i < f.size()) {
        ~~^~~~~~~~~~
bridge.cpp: In function 'std::vector<long long int> solve(std::function<bool(int, int)>)':
bridge.cpp:41:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0, j = 0; i < sums.size(); i++) {
                        ~~^~~~~~~~~~~~~
bridge.cpp:42:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(j < a.size() && comp(a[j].first + a[j].second, sums[i])) {
         ~~^~~~~~~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:86:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < vals.size(); i++) mp[vals[i]] = i;
                 ~~^~~~~~~~~~~~~
bridge.cpp:98:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < sums.size(); i++) res[i] = res1[i] + res2[sums.size()-1-i];
                 ~~^~~~~~~~~~~~~

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