Submission #39866

#TimeUsernameProblemLanguageResultExecution timeMemory
39866nickyrioPalembang Bridges (APIO15_bridge)C++14
100 / 100
156 ms33172 KiB
#include <bits/stdc++.h> #define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i) #define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b ; --i) #define REP(i, a) for (int i = 0, _a = (a); i < _a; ++i) #define pp pair<long long, long long> #define bit(S, i) (((S) >> i) & 1) #define next __next #define prev __prev #define N 1000030 using namespace std; int n, m, x1[N], x2[N]; vector<long long> ranking; vector<pp> e; priority_queue<long long> BottomMax; priority_queue<long long, vector<long long>, greater<long long> > TopMin; long long Left[N], Right[N]; void Solve() { while (!BottomMax.empty()) BottomMax.pop(); while (!TopMin.empty()) TopMin.pop(); // Median is top of BottomMax long long Low = 0, High = 0; REP(i, n) { BottomMax.push(x1[e[i].second]); BottomMax.push(x2[e[i].second]); Low += x1[e[i].second]; Low += x2[e[i].second]; while (BottomMax.size() - TopMin.size() > 1) { TopMin.push(BottomMax.top()); Low -= BottomMax.top(); High += BottomMax.top(); BottomMax.pop(); if (!BottomMax.empty() && TopMin.top() < BottomMax.top()) { BottomMax.push(TopMin.top()); Low += TopMin.top(); High -= TopMin.top(); TopMin.pop(); } } Right[i] = BottomMax.top() * BottomMax.size() - Low + High - BottomMax.top() * TopMin.size(); } } int main() { ios::sync_with_stdio(false); cin.tie(NULL); int k; cin >> k >> n; long long init = 0; FOR(i, 1, n) { char label1, label2; cin >> label1 >> x1[i] >> label2 >> x2[i]; if (x1[i] > x2[i]) swap(x1[i], x2[i]); if (label1 == label2) { init += x2[i] - x1[i]; } else { e.push_back(pp(x1[i] + x2[i], i)); ranking.push_back(x1[i]); ranking.push_back(x2[i]); init++; } } //Initialization sort(ranking.begin(), ranking.end()); ranking.resize(unique(ranking.begin(), ranking.end()) - ranking.begin()); n = e.size(); sort(e.begin(), e.end()); m = ranking.size(); // Cal median from Left to Right Solve(); REP(i, n) Left[i] = Right[i]; // Cal median from Right to Left reverse(e.begin(), e.end()); Solve(); reverse(Right, Right + n); if (k == 1) cout << Left[n - 1] + init; else { long long best = Right[0]; REP(i, n - 1) best = min(best, Left[i] + Right[i + 1]); cout << best + init; } }
#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...