Submission #185618

#	Time	Username	Problem	Language	Result	Execution time	Memory
185618		dndhk	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	115 ms	8912 KiB

bridge

#include <bits/stdc++.h>

#define pb push_back

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAX_N = 100000;
int N, K;
ll ans = 0;

vector<pll> vt;
vector<pll> v;

void solve1(){
	ll sidx = 0, scnt = 0;
	for(int i=0; i<vt.size(); i++){
		v.pb({vt[i].first, 1});
		v.pb({vt[i].second, -1});
		sidx+=vt[i].first;
		scnt--;
	}
	sort(v.begin(), v.end());
	ll sum = -1;
	for(int i=0; i<v.size(); i++){
		//cout<<v[i].first<<" "<<2LL * (sidx+scnt*v[i].first)+ans<<endl;
		if(sum==-1 || sum>sidx+scnt*v[i].first){
			sum = sidx + scnt*v[i].first;
		}
		if(v[i].second==1){
			sidx-=v[i].first;
			scnt++;
		}else{
			scnt++;
			sidx-=v[i].first;
		}
	}
	if(sum!=-1)	ans += 2LL * sum;
}

bool sf1(pll a, pll b){
	return a.first+a.second<b.first+b.second;
}
bool sf2(pll a, pll b){
	return a.first+a.second>b.first+b.second;
}

ll cost[2][MAX_N+1];

priority_queue<ll> pq1;
priority_queue<ll, vector<ll>, greater<ll> > pq2;

void calc(int idx){
	while(!pq1.empty())	pq1.pop();
	while(!pq2.empty())	pq2.pop();
	cost[idx][1] = 0;
	ll h = 0;
	pq1.push(vt[0].first); pq2.push(vt[0].second);
	for(int i=1; i<vt.size(); i++){
		ll l = vt[i].first, r = vt[i].second;
		if(l>pq2.top()){
			h+=l-pq2.top();
			pq1.push(pq2.top());
			pq2.pop();
			pq2.push(l);
			pq2.push(r);
		}else if(r<pq1.top()){
			h+=pq1.top()-r;
			pq2.push(pq1.top());
			pq1.pop();
			pq1.push(r);
			pq1.push(l);
		}else{
			pq1.push(l);
			pq2.push(r);
		}
		cost[idx][i+1] = h;
	}
}

void solve2(){
	if(vt.empty())	return;
	sort(vt.begin(), vt.end(), sf1);
	calc(0);
	for(int j=0; j<vt.size()-1; j++){
		if(vt.size()-1-j<=j)	break;
		pll tmp = vt[j];
		vt[j] = vt[vt.size()-1-j];
		vt[vt.size()-1-j] = tmp;

	}
	calc(1);
	ll sum = cost[0][0] + cost[1][vt.size()];
	for(int j=1; j<=vt.size(); j++){
		sum = min(sum, cost[0][j] + cost[1][vt.size()-j]);
	}
	ans+=2LL*sum;
}

int main(){
	scanf("%d%d", &K, &N);
	for(int i=0; i<N; i++){
		getchar();
		char c1, c2; 
		int a, b;
		scanf("%c %d %c %d", &c1, &a, &c2, &b);
		if(c1==c2){
			ans+=(ll)(max(a, b) - min(a, b));
		}else{
			ans += (ll)(max(a, b) - min(a, b) + 1);
			vt.pb({(ll)min(a, b), (ll)max(a, b)});
		}
	}
	if(K==1){
		if(!vt.empty()){
			calc(0);
			ans += 2LL * (ll)cost[0][vt.size()];
		}
		//solve1();
	}else if(K==2){
		solve2();
	}
	cout<<ans;
	return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'void solve1()':
bridge.cpp:20:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<vt.size(); i++){
               ~^~~~~~~~~~
bridge.cpp:28:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v.size(); i++){
               ~^~~~~~~~~
bridge.cpp: In function 'void calc(int)':
bridge.cpp:62:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1; i<vt.size(); i++){
               ~^~~~~~~~~~
bridge.cpp: In function 'void solve2()':
bridge.cpp:88:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j=0; j<vt.size()-1; j++){
               ~^~~~~~~~~~~~
bridge.cpp:89:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(vt.size()-1-j<=j) break;
      ~~~~~~~~~~~~~^~~
bridge.cpp:97:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j=1; j<=vt.size(); j++){
               ~^~~~~~~~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:104: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:109:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%c %d %c %d", &c1, &a, &c2, &b);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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