oj.uz

Submission #1077020

# Submission time Handle Problem Language Result Execution time Memory
1077020 2024-08-26T20:57:14 Z asdfgrace Palembang Bridges (APIO15_bridge) C++17
22 / 100
 31 ms 5080 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:
starts > lb and ends < rb:
lb + rb <= x + y --> use x
else --> use y
that actually applies to everything
so you can already just sort by sum
and binary search the right bound
given the left bound
but how do you compare between left bounds

okok the hint is you just sort by sum
just iterate over the n or smth breakpoints & look for the min with 2p or smth...
HINT: the median is always optimal
*/
 
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 {
    sort(a.begin(), a.end(), [&] (array<int, 2> a1, array<int, 2> a2) {
      return a1[0] + a1[1] < a2[0] + a2[1];
    });
    vector<vector<multiset<int>>> s(2, vector<multiset<int>>(2));
    vector<vector<long long>> sum(2, vector<long long>(2, 0));
    function<void(int, int)> ins = [&] (int i, int x) {
      if (s[i][0].empty() || x <= *s[i][0].rbegin()) {
        s[i][0].insert(x);
        sum[i][0] += x;
        if (s[i][0].size() > s[i][1].size() + 1) {
          int mx = *s[i][0].rbegin();
          s[i][0].erase(s[i][0].find(mx));
          sum[i][0] -= mx;
          s[i][1].insert(mx);
          sum[i][1] += mx;
        }
      } else {
        s[i][1].insert(x);
        sum[i][1] += x;
        if (s[i][1].size() > s[i][0].size()) {
          int mn = *s[i][1].begin();
          s[i][1].erase(s[i][1].find(mn));
          sum[i][1] -= mn;
          s[i][0].insert(mn);
          sum[i][0] += mn;
        }
      }
      
    };
    function<void(int, int)> del = [&] (int i, int x) {
      if (x <= *s[i][0].rbegin()) {
        s[i][0].erase(s[i][0].find(x));
        sum[i][0] -= x;
        if (s[i][0].size() > s[i][1].size() + 1) {
          int mx = *s[i][0].rbegin();
          s[i][0].erase(s[i][0].find(mx));
          sum[i][0] -= mx;
          s[i][1].insert(mx);
          sum[i][1] += mx;
        }
      } else {
        s[i][1].erase(s[i][1].find(x));
        sum[i][1] -= x;
        if (s[i][1].size() > s[i][0].size()) {
          int mn = *s[i][1].begin();
          s[i][1].erase(s[i][1].find(mn));
          sum[i][1] -= mn;
          s[i][0].insert(mn);
          sum[i][0] += mn;
        }
      }
    };
    function<long long(int)> cost = [&] (int i) {
      if (s[i][0].empty()) return 0ll;
      long long med = *s[i][0].rbegin();
      return (med * (long long) s[i][0].size() - sum[i][0])
        + (sum[i][1] - med * (long long) s[i][1].size());
    };
    for (int i = 0; i < n; i++) {
      ins(1, a[i][0]);
      ins(1, a[i][1]);
    }
    long long best = cost(1);
    for (int i = 0; i < n - 1; i++) {
      del(1, a[i][0]);
      del(1, a[i][1]);
      ins(0, a[i][0]);
      ins(0, a[i][1]);
      best = min(best, cost(0) + cost(1));
    }
    cout << best + bsl << '\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 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 472 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 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 0 ms 348 KB Output is correct

Subtask #2
14.0 / 14.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 0 ms 472 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 488 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 604 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
12 Correct 16 ms 3544 KB Output is correct
13 Correct 31 ms 5020 KB Output is correct
14 Correct 23 ms 3800 KB Output is correct
15 Correct 18 ms 3036 KB Output is correct
16 Correct 22 ms 4240 KB Output is correct
17 Correct 22 ms 5080 KB Output is correct
18 Correct 25 ms 4568 KB Output is correct
19 Correct 30 ms 5048 KB Output is correct
20 Correct 22 ms 4488 KB Output is correct
21 Correct 28 ms 4824 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Runtime error 1 ms 576 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Runtime error 1 ms 604 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Runtime error 1 ms 604 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -