oj.uz

Submission #937434

# Submission time Handle Problem Language Result Execution time Memory
937434 2024-03-04T03:52:33 Z duckindog Palembang Bridges (APIO15_bridge) C++17
31 / 100
 2000 ms 15056 KB 
//from duckindog wth depression
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>

using namespace std;

const int N = 100'000 + 10;
int k, n;

long long bridge(vector<pair<int, int>> x) {
  int n = x.size();
  if (!n) return 0;
  set<int> pos;
  vector<int> a(n + 1), b(n + 1);
  for (int i = 1; i <= n; ++i) {
    a[i] = x[i - 1].first;
    b[i] = x[i - 1].second;
    pos.insert(a[i]); pos.insert(b[i]);
  }
  sort(a.begin(), a.end()); sort(b.begin(), b.end());

  vector<long long> da(n + 1), db(n + 1);
  for (int i = 1; i <= n; ++i) {
    da[i] = da[i - 1] + a[i];
    db[i] = db[i - 1] + b[i];
  }

  auto cal = [&](int i) {
    auto itA = upper_bound(a.begin(), a.end(), i) - a.begin() - 1,
         itB = upper_bound(b.begin(), b.end(), i) - b.begin() - 1;
    long long ret = 0;
    ret += 1ll * itA * i - da[itA] + da[n] - da[itA] - 1ll * i * (n - itA);
    ret += 1ll * itB * i - db[itB] + db[n] - db[itB] - 1ll * i * (n - itB);
    return ret;
  };

  long long ret = 1'000'000'000'000'000;

  for (const auto& i : pos) {
    if (i == *pos.begin()) continue;
    int l = *prev(pos.lower_bound(i));
    int r = i, it = l;
    while (l <= r) {
      int mid = l + r >> 1;
      if (cal(mid) >= cal(mid + 1)) l = it = mid + 1;
      else r = mid - 1;
    }
    ret = min(ret, cal(it));
  }
  if (n == 1) return abs(a[1] - b[1]);
  return ret;
}

pair<int, int> x[N];

int32_t main() {
  cin.tie(0)->sync_with_stdio(0);

  if (fopen("duck.inp", "r")) {
    freopen("duck.inp", "r", stdin);
    freopen("duck.out", "w", stdout);
  }
  cin >> k >> n;

  long long answer = 0;
  for (int i = 1; i <= n; ++i) {
    char A, B;
    cin >> A >> x[i].first >> B >> x[i].second;
    if (A != B) continue;
    answer += abs(x[i].first - x[i].second);
    i -= 1; n -= 1;
  }

  if (!n) {
    cout << answer << "\n";
    return 0;
  }

  sort(x + 1, x + n + 1);

  if (k == 1) {
    cout << bridge(vector<pair<int, int>>(x + 1, x + n + 1)) + answer + n << "\n";
    return 0;
  }

  sort(x + 1, x + n + 1, [&](auto a, auto b) {
    return a.first + a.second < b.first + b.second;
  });


  long long ret = 1'000'000'000'000'000;
  for (int i = 1; i <= n; ++i) {
    vector<pair<int, int>> lt(x + 1, x + i + 1),
                           rt(x + i + 1, x + n + 1);
    ret = min(ret, bridge(lt) + bridge(rt));
  }

  cout << ret + answer + n << "\n";

}

Compilation message

bridge.cpp: In function 'long long int bridge(std::vector<std::pair<int, int> >)':
bridge.cpp:44:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |       int mid = l + r >> 1;
      |                 ~~^~~
bridge.cpp: In function 'int32_t main()':
bridge.cpp:60:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |     freopen("duck.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:61:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |     freopen("duck.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
14.0 / 14.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 344 KB Output is correct
4 Correct 3 ms 604 KB Output is correct
5 Correct 3 ms 604 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 4 ms 604 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 3 ms 604 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 18 ms 4956 KB Output is correct
13 Correct 312 ms 15044 KB Output is correct
14 Correct 44 ms 5084 KB Output is correct
15 Correct 180 ms 9328 KB Output is correct
16 Correct 21 ms 5164 KB Output is correct
17 Correct 318 ms 15056 KB Output is correct
18 Correct 139 ms 14928 KB Output is correct
19 Correct 232 ms 14608 KB Output is correct
20 Correct 24 ms 5456 KB Output is correct
21 Correct 136 ms 15048 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 17 ms 516 KB Output is correct
5 Correct 4 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 20 ms 348 KB Output is correct
9 Correct 8 ms 344 KB Output is correct
10 Correct 14 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 6 ms 488 KB Output is correct

Subtask #4
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 1 ms 348 KB Output is correct
4 Correct 17 ms 348 KB Output is correct
5 Correct 4 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 19 ms 348 KB Output is correct
9 Correct 8 ms 344 KB Output is correct
10 Correct 17 ms 856 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 6 ms 556 KB Output is correct
13 Correct 21 ms 604 KB Output is correct
14 Correct 221 ms 600 KB Output is correct
15 Execution timed out 2060 ms 604 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #5
0 / 37.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 16 ms 484 KB Output is correct
5 Correct 5 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 25 ms 344 KB Output is correct
9 Correct 9 ms 348 KB Output is correct
10 Correct 14 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 6 ms 348 KB Output is correct
13 Correct 21 ms 604 KB Output is correct
14 Correct 216 ms 640 KB Output is correct
15 Execution timed out 2051 ms 616 KB Time limit exceeded
16 Halted 0 ms 0 KB -