Submission #80728

#	Time	Username	Problem	Language	Result	Execution time	Memory
80728		xiaowuc1	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	1232 ms	57392 KiB

bridge

#include <bits/stdc++.h>

/*
unsigned seed1 = std::chrono::system_clock::now().time_since_epoch().count();
mt19937 g1.seed(seed1);

ios_base::sync_with_stdio(false);
cin.tie(NULL);
*/
using namespace std;

const double PI = 2 * acos(0);

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<int, ll> pill;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef vector<vector<ll>> matrix;

char buf1[5];
char buf2[5];

ll onesolve(vector<pii>& v, int x) {
  ll ret = 0;
  for(pii out: v) {
    ret += abs(out.first-x) + abs(out.second-x);
  }
  return ret;
}

ll onesolve(vector<pii>& v) {
  if(v.empty()) return 0;
  vector<int> all;
  for(auto out: v) {
    all.push_back(out.first);
    all.push_back(out.second);
  }
  sort(all.begin(), all.end());
  return onesolve(v, all[all.size()/2]);
}

vector<int> allV;
class medianBIT {
  vector<ll> sumbit;
  vector<int> cntbit;
  map<int, int> lower;
  int lowersize;
  map<int, int> greater;
  int greatersize;
  ll totalSum;
  public:
  ll query() {
    if(totalSum == 0) return 0;
    int med = greater.begin()->first;
    int idx = lower_bound(allV.begin(), allV.end(), med) - allV.begin();
    pill x = _bit_query(idx);
    ll rhssum = totalSum - x.second;
    int rhsamt = greatersize + lowersize - x.first;
    ll ans = (med * (ll)x.first - x.second) + (rhssum - med * (ll)rhsamt);
    return ans;
  }
  void _rebalance() {
    while(greatersize - lowersize > 1) {
      int merge = greater.begin()->first;
      lower[merge]++;
      lowersize++;
      if(--greater[merge] == 0) greater.erase(merge);
      greatersize--;
    }
    while(lowersize > greatersize) {
      int merge = lower.rbegin()->first;
      if(--lower[merge] == 0) lower.erase(merge);
      lowersize--;
      greater[merge]++;
      greatersize++;
    }
    if(lowersize == 0) return;
    while(lower.rbegin()->first > greater.begin()->first) {
      int lowup = lower.rbegin()->first;
      int highdown = greater.begin()->first;
      if(--lower[lowup] == 0) lower.erase(lowup);
      greater[lowup]++;
      if(--greater[highdown] == 0) greater.erase(highdown);
      lower[highdown]++;
    }
  }
  medianBIT() {
    sumbit.resize(allV.size() + 2);
    cntbit.resize(allV.size() + 2);
    lower.clear();
    lowersize = 0;
    greater.clear();
    greatersize = 0;
    totalSum = 0;
  }
  void _bit_update(int idx, int val) {
    totalSum += val;
    idx++;
    while(idx < sumbit.size()) {
      sumbit[idx] += val;
      if(val > 0) cntbit[idx]++;
      else cntbit[idx]--;
      idx += idx & -idx;
    }
  }
  pill _bit_query(int idx) {
    idx++;
    ll sumret = 0;
    int cntret = 0;
    while(idx) {
      sumret += sumbit[idx];
      cntret += cntbit[idx];
      idx -= idx & -idx;
    }
    return {cntret, sumret};
  }
  void insert(int v) {
    if(lowersize == greatersize) {
      greatersize++;
      greater[v]++;
    }
    else {
      lowersize++;
      lower[v]++;
    }
    int idx = lower_bound(allV.begin(), allV.end(), v) - allV.begin();
    _bit_update(idx, v);
    _rebalance();
  }
  void erase(int v) {
    if(lower.count(v)) {
      if(--lower[v] == 0) lower.erase(v);
      lowersize--;
    }
    else {
      assert(greater.count(v));
      if(--greater[v] == 0) greater.erase(v);
      greatersize--;
    }
    int idx = lower_bound(allV.begin(), allV.end(), v) - allV.begin();
    _bit_update(idx, -v);
    _rebalance();
  }

};

bool piisort(pii a, pii b) {
  return a.first + a.second < b.first + b.second;
}

ll twosolve(vector<pii>& v) {
  if(v.empty()) return 0;
  for(auto out: v) {
    allV.push_back(out.first);
    allV.push_back(out.second);
  }
  sort(allV.begin(), allV.end());
  ll ret = onesolve(v, allV[allV.size()/2]);
  medianBIT lhs;
  medianBIT rhs;
  sort(v.begin(), v.end(), piisort);
  for(auto out: v) {
    rhs.insert(out.first);
    rhs.insert(out.second);
  }
  for(auto out: v) {
    rhs.erase(out.first);
    rhs.erase(out.second);
    lhs.insert(out.first);
    lhs.insert(out.second);
    ret = min(ret, lhs.query() + rhs.query());
  }
  return ret;
}

int main() {
  int k, n;
  scanf("%d%d\n", &k, &n);
  vector<pii> x;
  ll inc = 0;
  while(n--) {
    int a, b;
    scanf("%s %d %s %d\n", buf1, &a, buf2, &b);
    a++;
    b++;
    if(buf1[0] == buf2[0]) {
      inc += abs(b-a);
    }
    else {
      x.push_back({min(a,b), max(a,b)});
    }
  }
  if(k == 1) printf("%lld\n", onesolve(x) + inc + x.size());
  else printf("%lld\n", twosolve(x) + inc + x.size());
}

Compilation message (stderr)

bridge.cpp: In member function 'void medianBIT::_bit_update(int, int)':
bridge.cpp:101:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(idx < sumbit.size()) {
           ~~~~^~~~~~~~~~~~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:180:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d\n", &k, &n);
   ~~~~~^~~~~~~~~~~~~~~~~~
bridge.cpp:185:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s %d %s %d\n", buf1, &a, buf2, &b);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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