# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
937409 | 2024-03-04T02:57:13 Z | duckindog | Palembang Bridges (APIO15_bridge) | C++17 | 1 ms | 512 KB |
//from duckindog wth depression #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(); 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]); } 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; return 0; } }
Compilation message
# | 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 | Incorrect | 0 ms | 348 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | 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 | Incorrect | 0 ms | 348 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | 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 | Incorrect | 1 ms | 348 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | 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 | Incorrect | 0 ms | 344 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 512 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Incorrect | 0 ms | 348 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |