oj.uz

Submission #937399

# Submission time Handle Problem Language Result Execution time Memory
937399 2024-03-04T02:08:11 Z duckindog Palembang Bridges (APIO15_bridge) C++17
22 / 100
 311 ms 13460 KB 
//from duckindog wth depression
#include<bits/stdc++.h>

using namespace std;

const int N = 100'000 + 10;
int k, n;
int a[N], b[N];
long long da[N], db[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 >> a[i] >> B >> b[i];
    if (A != B) continue;
    answer += abs(b[i] - a[i]);
    i -= 1; n -= 1;
  }
  if (!n) {
    cout << answer << "\n";
    return 0;
  }
  sort(a + 1, a + n + 1); sort(b + 1, b + n + 1);
  set<int> pos;
  for (int i = 1; i <= n; ++i) {
    pos.insert(a[i]); pos.insert(b[i]);
    da[i] = da[i - 1] + a[i];
    db[i] = db[i - 1] + b[i];
  }

  auto cal = [&](int i) {
    auto itA = upper_bound(a + 1, a + n + 1, i) - a - 1,
         itB = upper_bound(b + 1, b + n + 1, i) - b - 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) ret = abs(a[1] - b[1]);

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

}

Compilation message

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

Subtask #1
8.0 / 8.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 3 ms 2396 KB Output is correct
5 Correct 4 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 5 ms 2396 KB Output is correct
8 Correct 3 ms 2396 KB Output is correct
9 Correct 3 ms 2636 KB Output is correct
10 Correct 2 ms 2396 KB Output is correct
11 Correct 2 ms 2396 KB Output is correct
12 Correct 14 ms 3412 KB Output is correct
13 Correct 311 ms 13460 KB Output is correct
14 Correct 34 ms 3928 KB Output is correct
15 Correct 189 ms 9044 KB Output is correct
16 Correct 21 ms 3924 KB Output is correct
17 Correct 302 ms 13456 KB Output is correct
18 Correct 136 ms 13460 KB Output is correct
19 Correct 233 ms 12856 KB Output is correct
20 Correct 24 ms 3924 KB Output is correct
21 Correct 131 ms 13436 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Incorrect 1 ms 2392 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Incorrect 1 ms 2396 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Incorrect 1 ms 2508 KB Output isn't correct
4 Halted 0 ms 0 KB -