Submission #697770

#	Time	Username	Problem	Language	Result	Execution time	Memory
697770		ajstillpracticin	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	85 ms	5664 KiB

bridge

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define fi first
#define se second
#define pb push_back

#define sz(x) int((x).size())

int dx[4]{-1,0,1,0};
int dy[4]{0,1,0,-1};

void setIO(string filename=""){
	ios_base::sync_with_stdio(0); cin.tie(0);
	if(filename.size()){
		freopen((filename + ".in").c_str(), "r", stdin);
		freopen((filename + ".out").c_str(), "w", stdout);
	}
}

struct dsu {
	vector<int> e;
	dsu(int N) { e=vector<int>(N,-1); }

	int get(int x) { return e[x]<0 ? x : e[x]=get(e[x]); }

	bool same_set(int a, int b) { return get(a)==get(b); }

	int size(int x) { return -e[get(x)]; }

	bool unite(int x, int y){
		x=get(x),y=get(y);
		if(x==y) return false;
		if(e[x] > e[y]) swap(x,y);
		e[x]+=e[y]; e[y]=x; return true;
	}
};

const int INF=(int) 1e9;
const int M= 1e9+7;
const ll MAXD = 1e18;
const int P = 1e6;

//
const int MAXN = 1e5+5;

ll pref[MAXN];
ll rsum,lsum;

priority_queue<int> lpq;
priority_queue<int,vector<int>,greater<int>> rpq;

bool cmp(pair<int,int> a, pair<int,int> b) {
	return a.fi + a.se < b.fi + b.se;
}

void insert(int x){
	int median=(lpq.size() ? lpq.top() : INF);
	if(x <= median) {
		lpq.push(x);
		lsum+=x;
	} else {
		rpq.push(x);
		rsum+=x;
	}

	if(rpq.size() + 1 < lpq.size()){
		int nxt=lpq.top();
		lpq.pop();
		rpq.push(nxt);
		lsum-=nxt;
		rsum+=nxt;
	} else if(lpq.size() < rpq.size()){
		int nxt=rpq.top();
		rpq.pop();
		lpq.push(nxt);
		rsum-=nxt;
		lsum+=nxt;
	}
}

int main() {

	setIO();

	int k,n;
	cin >> k >> n;

	ll same_side=0;
	vector<pair<int,int>> v={{0,0}};
	for(int i=0;i<n;++i){
		char a,b;
		int x,y;
		cin >> a >> x >> b >> y;
		if(a==b)
			same_side += abs(x-y);
		else
			v.push_back({x,y});
	}

	sort(v.begin(),v.end(),cmp);
	n=v.size()-1;
	same_side+=n;

	lsum = rsum = 0;
	for(int i=1;i<=n;++i){
		insert(v[i].fi);
		insert(v[i].se);
		pref[i] = rsum - lsum;
	}

	ll ans=pref[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].fi);
			insert(v[i].se);
			ans=min(ans, rsum-lsum + pref[i-1]);
		}
	}

	cout << same_side + ans << "\n";
}

Compilation message (stderr)

bridge.cpp: In function 'void setIO(std::string)':
bridge.cpp:17:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |   freopen((filename + ".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:18:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |   freopen((filename + ".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