Submission #1101025

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101025		coolsentenceidontremember	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	72 ms	5716 KiB

bridge

#include"bits/stdc++.h"
#define ll long long
#define ld long double
#define ff first
#define ss second
#define pii pair<int, int>
#define mp make_pair
#define make_rng mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define make_rng64 mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count())
using namespace std;

void setIO(string s = ""){
 ios_base::sync_with_stdio(false);
 cin.tie(nullptr);
 cout.tie(nullptr);
 if (!s.empty()){
	freopen((s+".in").c_str(), "r", stdin);
	freopen((s+".out").c_str(), "w", stdout);
	}
}

const double PI = acos(-1);

struct chash{
	const uint64_t C = uint64_t(2e18 * PI) + 71;
	const uint32_t random = chrono::steady_clock::now().time_since_epoch().count();
	size_t operator()(uint64_t x) const {
		return __builtin_bswap64((x^random)*C);
	}
};

const int N = 1e5 + 1;



bool cmp(const pii &a, const pii &b){
	return a.ff + a.ss < b.ff + b.ss;
}

ll pfx[N];

priority_queue<int> lpq, rpq;

ll lsum, rsum;

void insert(int x){
	int med = (lpq.size() ? lpq.top() : INT_MAX);
	if (x <= med){
		lpq.push(x);
		lsum += x;
	} else {
		rpq.push(-x);
		rsum += x;
	}
	
	if (lpq.size() < rpq.size()){
		int a = -rpq.top();
		rpq.pop();
		lpq.push(a);
		lsum += a; rsum -= a;
	} else if (lpq.size() - rpq.size() > 1){
		int a = lpq.top();
		lpq.pop();
		rpq.push(-a);
		lsum -= a; rsum += a;
	}
	
}



int main(){
	setIO();
	int k, n;
	cin >> k >> n;
	ll same = 0;
	vector<pair<int, int>> v;
	for (int i = 1; i <= n; i++){
		char s1, s2;
		int s, t;
		cin >> s1 >> s >> s2 >> t;
		if (s1 == s2) same += abs(s-t);
		else v.push_back(mp(s, t));
	}
	v.push_back({0, 0});
	sort(v.begin(), v.end(), cmp);
    n = v.size() - 1;
    pfx[0] = 0;
    lsum = rsum = 0;
    for (int i = 1;i <= n; i++){
    	insert(v[i].ff);
    	insert(v[i].ss);
    	pfx[i] = rsum - lsum;
	}
	ll ans = pfx[n];
	if (k == 2){
		while (lpq.size()) lpq.pop();
		while (rpq.size()) rpq.pop();
		lsum = rsum = 0;
		for (int i = n; i; i--){
			insert(v[i].ff);
			insert(v[i].ss);
			ans = min(ans, rsum - lsum + pfx[i-1]);
		}
	}
	if (v.empty()) ans = 0;
	cout << ans + same + v.size() - 1 << '\n';
	
}

Compilation message (stderr)

bridge.cpp: In function 'void setIO(std::string)':
bridge.cpp:21:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |  freopen((s+".in").c_str(), "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:22:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |  freopen((s+".out").c_str(), "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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