oj.uz

Submission #1010315

# Submission time Handle Problem Language Result Execution time Memory
1010315 2024-06-28T17:40:56 Z asdfgrace Palembang Bridges (APIO15_bridge) C++17
63 / 100
 2000 ms 16648 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 15 ms 2776 KB Output is correct
13 Correct 32 ms 2776 KB Output is correct
14 Correct 23 ms 2516 KB Output is correct
15 Correct 16 ms 1496 KB Output is correct
16 Correct 19 ms 2768 KB Output is correct
17 Correct 18 ms 2572 KB Output is correct
18 Correct 27 ms 2740 KB Output is correct
19 Correct 26 ms 2564 KB Output is correct
20 Correct 17 ms 2776 KB Output is correct
21 Correct 25 ms 2764 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 1 ms 484 KB Output is correct
10 Correct 2 ms 480 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 2 ms 348 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 484 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 2 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 3 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 3 ms 348 KB Output is correct
13 Correct 56 ms 624 KB Output is correct
14 Correct 95 ms 604 KB Output is correct
15 Correct 166 ms 656 KB Output is correct
16 Correct 3 ms 344 KB Output is correct
17 Correct 28 ms 348 KB Output is correct
18 Correct 24 ms 348 KB Output is correct
19 Correct 49 ms 620 KB Output is correct
20 Correct 186 ms 688 KB Output is correct
21 Correct 87 ms 604 KB Output is correct
22 Correct 216 ms 664 KB Output is correct
23 Correct 46 ms 600 KB Output is correct
24 Correct 175 ms 672 KB Output is correct

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 2 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 472 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 2 ms 344 KB Output is correct
13 Correct 103 ms 612 KB Output is correct
14 Correct 89 ms 604 KB Output is correct
15 Correct 174 ms 604 KB Output is correct
16 Correct 3 ms 348 KB Output is correct
17 Correct 28 ms 348 KB Output is correct
18 Correct 21 ms 348 KB Output is correct
19 Correct 44 ms 612 KB Output is correct
20 Correct 219 ms 2836 KB Output is correct
21 Correct 109 ms 604 KB Output is correct
22 Correct 233 ms 600 KB Output is correct
23 Correct 60 ms 604 KB Output is correct
24 Correct 179 ms 672 KB Output is correct
25 Execution timed out 2067 ms 16648 KB Time limit exceeded
26 Halted 0 ms 0 KB -