Submission #1010315

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010315		asdfgrace	Palembang Bridges (APIO15_bridge)	C++17	63 / 100	2067 ms	16648 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
 
#define dbg(x) x
#define prt(x) dbg(cerr << x)
#define pv(x) dbg(cerr << #x << " = " << x << '\n')
#define pv2(x) dbg(cerr << #x << " = " << x.first << ',' << x.second << '\n')
#define parr(x) dbg(prt(#x << " = { "); for (auto y : x) prt(y << ' '); prt("}\n");)
#define parr2(x) dbg(prt(#x << " = { "); for (auto [y, z] : x) prt(y << ',' << z << "  "); prt("}\n");)
#define parr2d(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr(arr);} prt('\n'));
#define parr2d2(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr2(arr);} prt('\n'));
 
/*
build 1 or 2 bridges
add to baseline of sum of all distances driven without crossing bridge + n
then only consider people crossing
 
k=1:
minimize the sum of all abs(s[i] - x) + abs(t[i] - x)
one of the given locs is optimal
so here treat all s[i] and t[i] the same, sort, etc.
 
k=2:
if l <= x or y <= r, dist = r - l
else, dist = r - l + 2 * (dist btwn either end & closest bridge)
assume x < y
5 cases
1) left of x
2) contains x
3) btwn x, y
4) contains y
5) right of y
best y for each x?
everything to left/containing x is handled (i.e. everything with l <= x)
n^2 sol:
for each lb
consider the rb
and update as we go maybe with set or smth
probably maintain 3 sets or smth?
like 1 set of things ending on the left of x or containing x
these don't change
everything else ends after x
as y moves to the right
sets of things that start after x
1) starts on the right of y/containing y --> automatically use y
2) x on left and y on right --> use y if r is closer to y tha x is to l
can maintain 2 sets
when y moves to the right of a segment that used to contain it
(sort other set by rb and pop elems)
move it to the "y closer" set
probs for each elem
binary search where you would update that
and don't even maintain a set for case 2
*/
 
int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int k, n;
  cin >> k >> n;
  vector<array<int, 2>> a;
  long long bsl = 0;
  for (int i = 0; i < n; i++) {
    char c1, c2; int i1, i2;
    cin >> c1 >> i1 >> c2 >> i2;
    if (c1 == c2) {
      bsl += abs(i2 - i1);
    } else {
      if (i2 < i1) swap(i1, i2);
      a.push_back({i1, i2});
      bsl++;
    }
  }
  n = (int) a.size();
  if (n == 0) {
    cout << bsl << '\n';
    return 0;
  }
  vector<int> b;
  for (int i = 0; i < n; i++) {
    b.push_back(a[i][0]); b.push_back(a[i][1]);
  }
  sort(b.begin(), b.end());
  if (k == 1) {
    long long sum = 0;
    for (int i = 0; i < 2 * n; i++) {
      sum += b[i] - b[0];
    }
    long long best = sum;
    for (int i = 1; i < 2 * n; i++) {
      sum += (long long) i * (b[i] - b[i - 1]);
      sum -= (long long) (2 * n - i) * (b[i] - b[i - 1]);
      best = min(best, sum);
    }
    cout << best + bsl << '\n'; 
  } else {
    long long best = 1e18;
    for (int x = 0; x < 2 * n - 1; x++) {
      long long lx = 0, r1 = 0, r2 = 0, r3 = 0, r4 = 0;
      int c1 = 0, c2 = 0, c3 = 0, c4 = 0;
      vector<vector<int>> at1(2 * n), at2(2 * n), at3(2 * n);
      for (int i = 0; i < n; i++) {
        if (a[i][0] <= b[x]) {
          lx += abs(a[i][0] - b[x]) + abs(a[i][1] - b[x]);
        } else {
          r1 += abs(a[i][0] - b[x]) + abs(a[i][1] - b[x]);
          c1++;
          at1[lower_bound(b.begin(), b.end(), a[i][0]) - b.begin()].push_back(i);
          at2[lower_bound(b.begin(), b.end(), a[i][1]) - b.begin()].push_back(i);
          if (b[2 * n - 1] >= a[i][1] + (a[i][0] - b[x])) {
            at3[lower_bound(b.begin(), b.end(), a[i][1] + (a[i][0] - b[x])) - b.begin()].push_back(i);
          }
        }
      }
      for (int y = x + 1; y < 2 * n; y++) {
        r1 -= 2ll * c1 * (b[y] - b[y - 1]);
        r3 += 2ll * c3 * (b[y] - b[y - 1]);
        for (auto i : at1[y]) {
          r1 -= (long long) a[i][1] + a[i][0] - 2ll * b[y]; c1--;
          r2 += a[i][1] - a[i][0]; c2++;
        }
        for (auto i : at2[y]) {
          r2 -= a[i][1] - a[i][0]; c2--;
          r3 += 2ll * b[y] - (a[i][0] + a[i][1]); c3++;
        }
        for (auto i : at3[y]) {
          r3 -= 2ll * b[y] - (a[i][0] + a[i][1]); c3--;
          r4 += (long long) a[i][0] + a[i][1] - 2ll * b[x]; c4++;
        }
        best = min(best, bsl + lx + r1 + r2 + r3 + r4);
      }
    }
    cout << best << '\n';
  }
}
 
/*
any observations help
 
check every line
IF YOUR LINES AREN'T WRONG
CHECK IF YOUR LINES ARE IN THE RIGHT ORDER
 
NEVER GIVE UP
*/

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