Submission #1295112

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295112		picrad	Palembang Bridges (APIO15_bridge)	C++20	0 / 100	1 ms	572 KiB

bridge

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
using namespace std;
typedef long long ll;
typedef double dbl;
typedef pair<ll,ll> pii;
 
const int maxn = 1e5+5;
ll K,N,sum,cnt = 1e9+5,a,b,asum;
char c,d;
vector<pii> swp;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> K >> N;
  int temp = 0;
  for(int i =1; i <= N;i++){
    cin >> c >> a >> d >> b;
    sum += abs(a-b);
    if(c == d){
      temp++;
      continue;
    }
    asum += a;
    if(a > b)swap(a,b);
    swp.pb({a,0});
    swp.pb({b,1});
  }
  sort(swp.begin(),swp.end());
  ll l = 0, r = asum,posl = 0,posr = N-temp,i = 0,prv = 0;
  pii cur;
  while(i < swp.size()){
    cur = swp[i];
    r -= (cur.fi-prv)*posr;
    l += (cur.fi-prv)*posl;
    cnt = min(cnt,l+r);
    //cout << "DIST: " << cur.fi << "-" << prv << endl <<  cnt << " " << l  << " " <<  r  << endl;
    if(cur.se == 0)posr--;
    else posl++;
    while(i+1 < swp.size() && swp[i+1].fi == cur.fi){
      if(swp[i+1].se == 0)posr--;
      else posl++;
      i++;
    }
    i++;
    prv = cur.fi;
  }
  cout << sum + cnt*2 + N - temp<< endl;
}

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