제출 #772251

#제출 시각아이디문제언어결과실행 시간메모리
772251radoslav11Potatoes and fertilizers (LMIO19_bulves)C++17
30 / 100
193 ms39408 KiB
#include <iostream> #include <set> #include <cassert> #include <numeric> #define endl '\n' typedef long long ll; struct slope_trick { const ll inf = 9223372036854775807ll; std::multiset < ll > left_set, right_set; ll height; slope_trick() { height = 0; } ll get_right() { if (right_set.empty()) return inf; return *right_set.begin(); } ll get_left() { if (left_set.empty()) return -inf; return *left_set.rbegin(); } void add_basic(ll v) { ll left = get_left(), right = get_right(); if (v >= left && v <= right) { left_set.insert(v); right_set.insert(v); } else if (v < left) { left_set.insert(v); left_set.insert(v); right_set.insert(left); left_set.erase(left_set.find(left)); height = height + abs(v - left); } else assert(false); } void prefix_minimum() { right_set.clear(); } ll query_vlaue(ll debit) { ll last = get_left(), slope = 0, base = height; while(left_set.size() > 0 && get_left() > debit) { ll distance = last - get_left(); base = base + distance * slope; slope++; last = last - distance; assert(left_set.size() > 0); left_set.erase(prev(left_set.end())); } if (slope != 0) { assert(last >= debit); base = base + (last - debit) * slope; } return base; } }; const int maxn = 500010; int n; ll a[maxn], b[maxn]; ll x[maxn], pref[maxn]; void solve() { std::cin >> n; for (int i = 1; i <= n; i++) { std::cin >> a[i] >> b[i]; x[i] = a[i] - b[i]; pref[i] = pref[i - 1] + x[i]; } slope_trick st; ll cnt = 0; for (int i = 1; i <= n; i++) { if (pref[i] < 0) { st.height += -pref[i]; st.add_basic(0); } else st.add_basic(pref[i]); st.prefix_minimum(); } ll ans = st.query_vlaue(pref[n]); std::cout << ans << endl; } void speed() { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(NULL); } signed main() { speed(); solve(); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

bulves.cpp: In function 'void solve()':
bulves.cpp:90:8: warning: unused variable 'cnt' [-Wunused-variable]
   90 |     ll cnt = 0;
      |        ^~~
#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...