Submission #810834

#	Time	Username	Problem	Language	Result	Execution time	Memory
810834		abczz	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	286 ms	16712 KiB

bridge

#include <iostream>
#include <vector>
#include <array>
#include <cstdlib>
#include <algorithm>
#include <map>
#define ll long long

using namespace std;

char C, D;
multimap <ll, ll> mp, mp2;
vector <ll> X;
vector <array<ll, 2> > V;
ll k, n, l, r, f, mn = 1e18, t, sl, sr, tl, tr;

int main() {
  cin >> k >> n;
  if (k == 1) {
    for (int i=0; i<n; ++i) {
      cin >> C >> l >> D >> r;
      if (l > r) swap(l, r);
      if (C == D) f += r-l;
      else {
        X.push_back(l);
        X.push_back(r);
      }
    }
    sort(X.begin(), X.end());
    for (auto u : X) {
      f += abs(X[X.size()/2]-u);
    }
    cout << f+X.size()/2 << '\n';
    return 0;
  }
  for (int i=0; i<n; ++i) {
    cin >> C >> l >> D >> r;
    if (l > r) swap(l, r);
    if (C == D) f += r-l;
    else V.push_back({l, r});
  }
  sort(V.begin(), V.end(), [](auto a, auto b) {
    return a[0]+a[1] < b[0]+b[1];
  });
  if (V.size() == 1) f += V[0][1]-V[0][0]+1;
  if (V.size() <= 1) {
    cout << f << '\n';
    return 0;
  }
  for (int i=0; i<V.size(); ++i) {
    mp2.insert({V[i][0], i});
    mp2.insert({V[i][1], i});
    t += V[i][0]+V[i][1];
  }
  auto md = mp.begin();
  auto md2 = mp2.begin();
  for (int i=0; i<V.size()-1; ++i) {
    sl += md2->first;
    md2 = next(md2);
  }
  sl += md2->first;
  sr = t-sl;
  for (int i=0; i<V.size()-1; ++i) {
    mp.insert({V[i][0], i});
    mp.insert({V[i][1], i});
    if (i) {
      if (V[i][1] < md->first) {
        tl -= md->first;
        tr += md->first;
        md = prev(md);
        tl += V[i][0]+V[i][1];
      }
      else if (V[i][0] >= md->first) {
        md = next(md);
        tl += md->first;
        tr -= md->first;
        tr += V[i][0]+V[i][1];
      }
      else tl += V[i][0], tr += V[i][1];
    }
    else {
      md = mp.begin();
      tl += V[i][0], tr += V[i][1];
    }
    if (V[i][0] == V[i][1] && V[i][0] == md2->first) {
      auto z = prev(md2);
      if (z->first != md2->first) {
        sl -= md2->first;
        sr += md2->first;
        md2 = prev(md2);
        sr -= V[i][0]+V[i][1];
      }
      else {
        md2 = next(md2);
        sl += md2->first;
        sr -= md2->first;
        sl -= V[i][0]+V[i][1];
      }
    }
    else if (V[i][1] <= md2->first) {
      md2 = next(md2);
      sl += md2->first;
      sr -= md2->first;
      sl -= V[i][0]+V[i][1];
    }
    else if (md2->first <= V[i][0]) {
      sl -= md2->first;
      sr += md2->first;
      md2 = prev(md2);
      sr -= V[i][0]+V[i][1];
    }
    else sl -= V[i][0], sr -= V[i][1];
    mp2.erase(mp2.lower_bound(V[i][0]));
    mp2.erase(mp2.lower_bound(V[i][1]));
    mn = min(mn, ((md->first+next(md)->first)/2)*((ll)mp.size()/2)-tl+tr-((md->first+next(md)->first)/2)*((ll)mp.size()/2)+
            ((md2->first+next(md2)->first)/2)*((ll)mp2.size()/2)-sl+sr-((md2->first+next(md2)->first)/2)*((ll)mp2.size()/2));
  }
  cout << mn+V.size()+f << '\n';
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:50:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   for (int i=0; i<V.size(); ++i) {
      |                 ~^~~~~~~~~
bridge.cpp:57:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |   for (int i=0; i<V.size()-1; ++i) {
      |                 ~^~~~~~~~~~~
bridge.cpp:63:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   for (int i=0; i<V.size()-1; ++i) {
      |                 ~^~~~~~~~~~~

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