Submission #700623

#	Time	Username	Problem	Language	Result	Execution time	Memory
700623		Abrar_Al_Samit	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	117 ms	9048 KiB

bridge

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

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

  long long ans = 0, S = 0;

  int s[n], t[n];

  vector<int>pts;

  vector<pair<int,int>>a, b;
  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 {
      a.emplace_back(s[i], t[i]);
      b.emplace_back(t[i], s[i]);
      pts.push_back(s[i]);
      pts.push_back(t[i]);
      S += t[i] - s[i];
    }
  }
  sort(a.begin(), a.end());
  sort(b.begin(), b.end());

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

  ans += n;

  long long pre[n], suf[n];
  long long p1[n], s1[n];
  for(int i=0; i<n; ++i) {
    pre[i] = -(b[i].first+b[i].second);
    p1[i] = b[i].first-b[i].second;
    if(i) {
      pre[i] += pre[i-1];
      p1[i] += p1[i-1];
    }
  }

  for(int i=n-1; i>=0; --i) {
    suf[i] = a[i].first+a[i].second;
    s1[i] = a[i].second-a[i].first;
    if(i<n-1) {
      suf[i] += suf[i+1];
      s1[i] += s1[i+1];
    }
  }

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

  int m = pts.size();

  long long best = INF;
  for(int x : pts) {
    int j1 = ub(b.begin(), b.end(), make_pair(x, -1)) - b.begin() - 1;
    int j2 = ub(a.begin(), a.end(), make_pair(x, -1)) - a.begin();

    int c1 = j1+1, c2 = (n-j2);

    long long cur = S;
    if(c1) {
      cur += pre[j1] + c1 * 2LL * x;
      cur -= p1[j1];
    }
    if(c2) {
      cur += suf[j2] - c2 * 2LL * x;
      cur -= s1[j2];
    }
    best = min(best, cur);
  }
  ans += best;
  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:66:7: warning: unused variable 'm' [-Wunused-variable]
   66 |   int m = pts.size();
      |       ^

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