# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
772223 | 2023-07-03T18:26:30 Z | danikoynov | Potatoes and fertilizers (LMIO19_bulves) | C++14 | 173 ms | 40416 KB |
#include <iostream> #include <set> #include <cassert> #include <numeric> #define endl '\n' #define int long long typedef long long ll; const int BUFF_SIZE = 1e6; int buffPos = BUFF_SIZE - 1; char buff[BUFF_SIZE]; void readChar() { if (++buffPos == BUFF_SIZE) fread(buff, BUFF_SIZE, 1, stdin), buffPos = 0; } void readInt(int &num) { num = 0; for (; '0' > buff[buffPos] || buff[buffPos] > '9' ; readChar()); for (; '0' <= buff[buffPos] && buff[buffPos] <= '9' ; readChar()) num = 10 * num + buff[buffPos] - '0'; } struct slope_trick { const ll inf = 1e18; std::multiset < ll > left_set, right_set; ll height; slope_trick() { height = 0; } void add_basic(ll v) /// adds |x - v| { ll left = -inf; ll right = inf; if (!left_set.empty()) left = *left_set.rbegin(); if (!right_set.empty()) right = *right_set.begin(); if (v >= left && v <= right) /// function on base { left_set.insert(v); right_set.insert(v); } else if (v < left) { left_set.erase(left_set.find(left)); right_set.insert(left); left_set.insert(v); left_set.insert(v); height = height + abs(left - v); } else if (v > right) { ///std::cout << v << " " << right << endl; right_set.erase(right_set.begin()); left_set.insert(right); right_set.insert(v); right_set.insert(v); height = height + abs(right - v); } } void print_slope_trick() { std::cout << "left_slope" << endl; for (int cor : left_set) std::cout << cor << " "; std::cout << endl; std::cout << "right_slope" << endl; for (int cor : right_set) std::cout << cor << " "; std::cout << endl; std::cout << "height " << height << endl; } 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 prefix_minimum() { while(left_set.size() > 0) { ll val = *left_set.begin(); if (val >= 0) break; assert(left_set.size() > 0); left_set.erase(left_set.find(val)); } ll slope = 0, base = height, last = get_right(); while (get_right() <= 0) { ll distance = get_right() - last; base = base + distance * slope; slope ++; last = last + distance; assert(right_set.size() > 0); right_set.erase(right_set.begin()); } if (slope != 0) { base = base + (- last) * slope; right_set.insert(0); } height = base; right_set.clear(); ///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(left_set.find(*left_set.rbegin())); } if (slope != 0) { base = base + (last - debit) * slope; } return base; } }; const int maxn = 500010; int n; int a[maxn], b[maxn]; ll x[maxn], pref[maxn]; void solve() { readInt(n); for (int i = 1; i <= n; i ++) { readInt(a[i]); readInt(b[i]); x[i] = a[i] - b[i]; pref[i] = pref[i - 1] + x[i]; } slope_trick st; for (int i = 1; i <= n; i ++) { st.add_basic(pref[i]); st.prefix_minimum(); //std::cout << "--------------------" << endl; //st.print_slope_trick(); } ///std::cout << "dasdas" << endl; ll ans = st.query_vlaue(pref[n]); ///std::cout << "-----------------" << endl; 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; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 596 KB | Output is correct |
3 | Correct | 1 ms | 468 KB | Output is correct |
4 | Correct | 15 ms | 3232 KB | Output is correct |
5 | Correct | 29 ms | 6208 KB | Output is correct |
6 | Correct | 96 ms | 20412 KB | Output is correct |
7 | Correct | 78 ms | 18288 KB | Output is correct |
8 | Incorrect | 173 ms | 40416 KB | Output isn't correct |
9 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 596 KB | Output is correct |
3 | Correct | 1 ms | 468 KB | Output is correct |
4 | Correct | 15 ms | 3232 KB | Output is correct |
5 | Correct | 29 ms | 6208 KB | Output is correct |
6 | Correct | 96 ms | 20412 KB | Output is correct |
7 | Correct | 78 ms | 18288 KB | Output is correct |
8 | Incorrect | 173 ms | 40416 KB | Output isn't correct |
9 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 596 KB | Output is correct |
3 | Correct | 0 ms | 340 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 1 ms | 468 KB | Output is correct |
6 | Correct | 1 ms | 596 KB | Output is correct |
7 | Correct | 1 ms | 596 KB | Output is correct |
8 | Correct | 1 ms | 596 KB | Output is correct |
9 | Correct | 1 ms | 596 KB | Output is correct |
10 | Correct | 1 ms | 596 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 596 KB | Output is correct |
3 | Correct | 1 ms | 468 KB | Output is correct |
4 | Correct | 0 ms | 340 KB | Output is correct |
5 | Correct | 1 ms | 340 KB | Output is correct |
6 | Correct | 1 ms | 468 KB | Output is correct |
7 | Correct | 1 ms | 596 KB | Output is correct |
8 | Correct | 1 ms | 596 KB | Output is correct |
9 | Correct | 1 ms | 596 KB | Output is correct |
10 | Correct | 1 ms | 596 KB | Output is correct |
11 | Correct | 1 ms | 596 KB | Output is correct |
12 | Correct | 1 ms | 468 KB | Output is correct |
13 | Correct | 1 ms | 596 KB | Output is correct |
14 | Correct | 2 ms | 596 KB | Output is correct |
15 | Correct | 2 ms | 596 KB | Output is correct |
16 | Correct | 1 ms | 596 KB | Output is correct |
17 | Correct | 1 ms | 596 KB | Output is correct |
18 | Correct | 1 ms | 468 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 596 KB | Output is correct |
3 | Correct | 1 ms | 468 KB | Output is correct |
4 | Correct | 0 ms | 340 KB | Output is correct |
5 | Correct | 1 ms | 340 KB | Output is correct |
6 | Correct | 1 ms | 468 KB | Output is correct |
7 | Correct | 1 ms | 596 KB | Output is correct |
8 | Correct | 1 ms | 596 KB | Output is correct |
9 | Correct | 1 ms | 596 KB | Output is correct |
10 | Correct | 1 ms | 596 KB | Output is correct |
11 | Correct | 15 ms | 3232 KB | Output is correct |
12 | Correct | 29 ms | 6208 KB | Output is correct |
13 | Correct | 96 ms | 20412 KB | Output is correct |
14 | Correct | 78 ms | 18288 KB | Output is correct |
15 | Incorrect | 173 ms | 40416 KB | Output isn't correct |
16 | Halted | 0 ms | 0 KB | - |