Submission #585490

#TimeUsernameProblemLanguageResultExecution timeMemory
585490Tien_NoobPalembang Bridges (APIO15_bridge)C++17
22 / 100
222 ms14384 KiB
//Make CSP great again //Vengeance #include <bits/stdc++.h> #define TASK "TESTCODE" #define Log2(x) 31 - __builtin_clz(x) using namespace std; const int N = 1e5; int k, n; long long add, res = 1e18; set<int> pos; multiset<pair<int, int> > L, mid, R; int cnt[2]; long long sum[3]; void read() { cin >> k >> n; while(n--) { char P, Q; int s, t; cin >> P >> s >> Q >> t; if (P == Q) { add += abs(s - t); continue; } pos.insert(s); pos.insert(t); if (s > t) { swap(s, t); } L.insert({s, t}); //R.insert({t, s}); ++cnt[1]; sum[1] += s + t; ++add; } } vector<pair<int, int> > trash; long long Cal(int mid) { long long ret = 0; for (auto &p : trash) { ret += abs(p.first - mid) + abs(p.second - mid); } return ret; } long long Get() { /*int low = 0, high = 1e9; while(low <= high) { int mid = (low + high)/2; if (Cal(mid) >= Cal(mid + 1)) { low = mid + 1; } else { high = mid - 1; } } return min(Cal(low), Cal(high));*/ long long ret = 1e18; for (int x : pos) { ret = min(ret, Cal(x)); } return ret; } void solve() { if (k == 1) { if (pos.empty()) { cout << add; return ; } for (int x : pos) { while(!L.empty() && L.begin()->first <= x) { sum[2] += L.begin()->second - L.begin()->first; --cnt[1]; sum[1] -= L.begin()->first + L.begin()->second; mid.insert({L.begin()->second, L.begin()->first}); L.erase(L.begin()); } while(!mid.empty() && mid.begin()->first <= x) { ++cnt[0]; sum[0] += mid.begin()->first + mid.begin()->second; sum[2] -= mid.begin()->first - mid.begin()->second; mid.erase(mid.begin()); } res = min(res, 2LL * x * cnt[0] - sum[0] + sum[1] - 2LL * cnt[1] * x + sum[2]); } cout << res + add; } else { if (pos.empty()) { cout << add; return ; } for (int x : pos) { while(!L.empty() && L.begin()->first <= x) { sum[2] += L.begin()->second - L.begin()->first; --cnt[1]; sum[1] -= L.begin()->first + L.begin()->second; mid.insert({L.begin()->second, L.begin()->first}); L.erase(L.begin()); } while(!mid.empty() && mid.begin()->first <= x) { ++cnt[0]; sum[0] += mid.begin()->first + mid.begin()->second; sum[2] -= mid.begin()->first - mid.begin()->second; trash.push_back({mid.begin()->first, mid.begin()->second}); mid.erase(mid.begin()); } res = min(res, Get() + sum[1] - 2LL * cnt[1] * x + sum[2]); } cout << res + add; } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); if (fopen(TASK".INP", "r")) { freopen(TASK".INP", "r", stdin); //freopen(TASK".OUT", "w", stdout); } int t = 1; bool typetest = false; if (typetest) { cin >> t; } for (int __ = 1; __ <= t; ++ __) { //cout << "Case " << __ << ": "; read(); solve(); } }

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:139:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  139 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...