Submission #35665

#	Time	Username	Problem	Language	Result	Execution time	Memory
35665		funcsr	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	909 ms	11252 KiB

bridge

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
struct BIT {
  int n;
  vector<long long> xs;
  BIT (int n) : n(n) { xs.resize(n+1); }

  void add(int i, int v) {
    for (int x=i+1; x<=n; x+=x&-x) xs[x] += v;
  }
  long long sum(int i) {
    long long s = 0;
    for (int x=i+1; x>0; x-=x&-x) s += xs[x];
    return s;
  }
};

int K, N;
vector<int> xs;

vector<long long> solve(vector<P> ps) {
  vector<long long> ret;
  ret.pb(0);
  BIT sum(xs.size()), num(xs.size());
  long long cs = 0, total_sum = 0, total_num = 0;
  auto f = [&](long long X) {
    int p = (int)(upper_bound(all(xs), X) - xs.begin())-1;
    long long s = sum.sum(p), n = num.sum(p);
    return ((total_sum-s) - 1LL*X*(total_num-n)) + (1LL*X*n-s) + cs;
  };
  for (P p : ps) {
    int l = p._1-p._2, r = p._2;
    int lp = index(xs, l), rp = index(xs, r);
    // [l, r]
    // f(x) += |x-l| + |x-r| - (r-l)
    sum.add(lp, l), num.add(lp, 1);
    sum.add(rp, r), num.add(rp, 1);
    total_sum += l+r;
    total_num += 2;
    cs -= r-l;
    int lo = 0, hi = 1e9+5;
    while (hi - lo > 1) {
      int mid = (lo + hi) / 2;
      if (f(mid) - f(mid-1) <= 0) lo = mid;
      else hi = mid;
    }
    ret.pb(f(lo));
  }
  return ret;
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> K >> N;
  long long sum = 0;
  vector<P> ps;
  rep(i, N) {
    char a, b;
    int x, y;
    cin >> a >> x >> b >> y;
    if (x > y) swap(x, y);
    sum += y-x;
    if (a != b) {
      sum++,
      ps.pb(P(x+y, y));
    }
    xs.pb(x), xs.pb(y);
  }
  sort(all(xs)); uniq(xs);

  int n = ps.size();
  sort(all(ps));
  vector<long long> l = solve(ps);
  if (K == 1) {
    cout << sum + l[n] << "\n";
    return 0;
  }
  reverse(all(ps));
  vector<long long> r = solve(ps);
  long long m = 1LL<<60;
  rep(i, n+1) m = min(m, sum + l[i] + r[n-i]);
  cout << m << "\n";
  return 0;
}

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