#include <bits/stdc++.h>
#ifdef OP_DEBUG
#include <algo/debug.h>
#else
#define debug(...) 26
#endif
using namespace std;
#define int long long // maybe tle?
#define sz(v) (int)(v).size()
#define all(v) (v).begin(), (v).end()
#define TcT template <class T
const int MOD = (int)1e9 + 7, INF = (int)2e9 + 9, INF64 = (int)4e18 + 18;
TcT> bool minimize(T &val, const T &upd) { return upd < val ? val = upd, 1 : 0; }
TcT> bool maximize(T &val, const T &upd) { return upd > val ? val = upd, 1 : 0; }
TcT, class S> istream &operator >> (istream &scanf, pair <T, S> &u) { return scanf >> u.first >> u.second; }
TcT, class S> ostream &operator << (ostream &print, pair <T, S> &u) { return print << u.first << ' ' << u.second; }
void solve();
int32_t main() {
cin.tie(nullptr), cout.tie(nullptr) -> sync_with_stdio(0);
int testcases = 1;
#define TC 0
if (TC) { cin >> testcases; } for (; testcases--;) { solve(); }
}
/* [Pham Hung Anh - 11I - Tran Hung Dao High School for Gifted Student] */
const int N = 1e5 + 5;
int k, n;
int same_side;
vector <int> buildings;
vector <pair <int, int>> opposite;
namespace sub12 { // O(n)
void solve() {
int ans = same_side;
if (sz(buildings) == 0)
return void(cout << ans << '\n');
int m = sz(buildings);
int median = buildings[(m + 1) / 2];
for (int i = 0; i < m; ++i)
ans += abs(median - buildings[i]);
cout << ans + sz(buildings) / 2 << '\n';
}
}
namespace sub3 { // O(n^3)
void solve() {
int ans = same_side;
if (sz(buildings) == 0)
return void(cout << ans << '\n');
int res = INF64;
for (int i = 0; i < sz(buildings); ++i)
for (int j = i + 1; j < sz(buildings); ++j) {
int bridge1 = buildings[i], bridge2 = buildings[j];
int sum = 0;
for (auto p : opposite)
sum += min(abs(p.first - bridge1) + abs(p.second - bridge1), abs(p.first - bridge2) + abs(p.second - bridge2)) + 1;
minimize(res, sum);
}
cout << ans + res << '\n';
}
}
namespace sub4 { // O(log3(n)^2 * n)
int get(int bridge1, int bridge2) {
int sum = same_side;
for (auto p : opposite)
sum += min(abs(p.first - bridge1) + abs(p.second - bridge1), abs(p.first - bridge2) + abs(p.second - bridge2)) + 1;
return sum;
}
int ternary_search(int bridge1) {
int res = INF64;
int lo = bridge1 + 1, hi = sz(buildings) - 1;
while (lo <= hi) {
int mid1 = lo + (hi - lo) / 3;
int mid2 = hi - (hi - lo) / 3;
int sum1 = get(buildings[bridge1], buildings[mid1]);
int sum2 = get(buildings[bridge1], buildings[mid2]);
minimize(res, min(sum1, sum2));
if (sum1 < sum2)
hi = mid2 - 1;
else if (sum1 > sum2)
lo = mid1 + 1;
else
lo = mid1 + 1, hi = mid2 - 1;
}
return res;
}
void solve() {
int ans = INF64;
int lo = 0, hi = sz(buildings) - 2;
while (lo <= hi) {
int mid1 = lo + (hi - lo) / 3;
int mid2 = hi - (hi - lo) / 3;
int ans1 = ternary_search(mid1);
int ans2 = ternary_search(mid2);
minimize(ans, min(ans1, ans2));
if (ans1 < ans2)
hi = mid2 - 1;
else if (ans1 > ans2)
lo = mid1 + 1;
else
lo = mid1 + 1, hi = mid2 - 1;
}
cout << ans << '\n';
}
}
namespace sub5 {
int suml = 0, sumr = 0;
multiset <int> lo, hi;
void balance() {
while (sz(lo) > sz(hi)) {
int x = *lo.rbegin();
hi.emplace(x);
suml -= x;
sumr += x;
lo.erase(lo.find(x));
}
while (sz(hi) > sz(lo)) {
int x = *hi.begin();
lo.emplace(x);
suml += x;
sumr -= x;
hi.erase(hi.find(x));
}
}
void add(int x) {
lo.emplace(x);
suml += x;
balance();
}
void solve() {
sort(opposite.begin(), opposite.end(), [&](pair <int, int> opposite, pair <int, int> b) -> bool {
return opposite.first + opposite.second < b.first + b.second;
});
vector <int> pref(sz(opposite) + 1);
for(int i = 0; i < sz(opposite); ++i) {
add(opposite[i].first);
add(opposite[i].second);
pref[i + 1] = sumr - suml;
}
int ans = pref[sz(opposite)];
lo.clear();
hi.clear();
suml = sumr = 0;
for(int i = sz(opposite) - 1; i >= 0; --i) {
add(opposite[i].first);
add(opposite[i].second);
minimize(ans, pref[i] + sumr - suml);
}
cout << ans + sz(opposite) + same_side << '\n';
}
}
void solve() {
cin >> k >> n;
for (int i = 1; i <= n; ++i) {
char p, q; int s, t; cin >> p >> s >> q >> t;
if (p == q)
same_side += abs(s - t);
else
buildings.push_back(s), buildings.push_back(t),
opposite.emplace_back(min(s, t), max(s, t));
}
sort(all(buildings));
if (k == 1)
sub12 :: solve();
else {
if (n <= 100)
sub3 :: solve();
else if (n <= 1000)
sub4 :: solve();
else
sub5 :: solve();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
