Submission #700627

#	Time	Username	Problem	Language	Result	Execution time	Memory
700627		Abrar_Al_Samit	Palembang Bridges (APIO15_bridge)	C++17	41 / 100	2061 ms	30136 KiB

bridge

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

const long long INF = 1e18;
void PlayGround() {
  int k, n;
  cin>>k>>n;

  int s[n], t[n];

  vector<int>pts;
  long long ans = 0;

  for(int i=0; i<n; ++i) {
    char p, q;
    cin>>p>>s[i]>>q>>t[i];
    if(s[i]>t[i]) swap(s[i], t[i]);
    if(p==q) {
      ans += t[i] - s[i];
      --i;
      --n;
    } else {
      pts.push_back(s[i]);
      pts.push_back(t[i]);
    }
  }

  if(n==0) {
  	cout<<ans<<'\n';
  	return;
  }


  sort(pts.begin(), pts.end());
  pts.resize(unique(pts.begin(), pts.end())-pts.begin());

  int m = pts.size();

  long long best = INF;
  for(int i=0; i<m; ++i) {
  	int x = pts[i];

  	long long cur = 0;
  	map<int,int>come, gone;
  	vector<pair<int,int>>bag;
  	for(int j=0; j<n; ++j) {
  		if(s[j]>x) {
  			bag.emplace_back(s[j], t[j]);
  			come[s[j]]++;
  			gone[t[j]]--;
  		}
  		cur += abs(s[j]-x) + abs(t[j]-x);
  	}

  	set<int>new_pts;
  	for(int j=i; j<m; ++j) {
  		new_pts.insert(pts[j]);
  	}

  	for(int j=0; j<bag.size(); ++j) {
  		int new_point = bag[j].second + bag[j].first - x;
  		gone[new_point]++;
  		new_pts.insert(new_point);
  	}

  	int c1 = 0, c2 = bag.size();
  	while(!new_pts.empty()) {
  		int y = *new_pts.begin();
  		new_pts.erase(y);

  		best = min(best, cur);
  		if(new_pts.empty()) break;

  		int next_point = *new_pts.begin();
  		if(gone.count(y)) c1 -= gone[y];
  		if(come.count(y)) c2 -= come[y];

  		long long len = next_point - y;

  		cur += -c2 * 2 * len + c1 * 2 * len;
  	}
  }	

  ans += best + n;
  cout<<ans<<'\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  PlayGround();
  return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'void PlayGround()':
bridge.cpp:60:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |    for(int j=0; j<bag.size(); ++j) {
      |                 ~^~~~~~~~~~~

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