제출 #807604

#제출 시각아이디문제언어결과실행 시간메모리
807604peijarPalembang Bridges (APIO15_bridge)C++17
0 / 100
1 ms468 KiB
#include <bits/stdc++.h> #define int long long using namespace std; string to_string(string s) { return s; } template <typename T> string to_string(T v) { bool first = true; string res = "["; for (const auto &x : v) { if (!first) res += ", "; first = false; res += to_string(x); } res += "]"; return res; } void dbg_out() { cout << endl; } template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << to_string(H); dbg_out(T...); } #ifdef DEBUG #define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__) #else #define dbg(...) #endif struct Median { priority_queue<int> lower; priority_queue<int, vector<int>, greater<int>> upper; int sumLow, sumUp; Median() : sumLow(0), sumUp(0) {} void add(int x) { if (!lower.empty() and lower.top() < x) upper.push(x), sumUp += x; else lower.push(x), sumLow += x; while (upper.size() > lower.size()) { sumUp -= upper.top(); sumLow += upper.top(); lower.push(upper.top()); upper.pop(); } while (lower.size() > upper.size() + 1) { sumLow -= lower.top(); sumUp += lower.top(); upper.push(lower.top()); lower.pop(); } } int med() { int x = lower.top(); return x * lower.size() - sumLow + sumUp - x * upper.size(); } }; signed main(void) { ios_base::sync_with_stdio(false); cin.tie(0); int K, N; cin >> K >> N; if (K == 1) { vector<pair<int, int>> intervals; int sol = 0; for (int i = 0; i < N; ++i) { char c, d; int a, b; cin >> c >> a >> d >> b; if (a > b) swap(a, b); if (c == d) { sol += b - a; continue; } intervals.emplace_back(a, b); } Median med; for (auto [a, b] : intervals) { med.add(a); med.add(b); } dbg(sol, med.med()); cout << sol + med.med() + intervals.size() << endl; } else { } }
#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...