| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 772211 | 2023-07-03T18:13:31 Z | danikoynov | Potatoes and fertilizers (LMIO19_bulves) | C++14 | 0 ms | 0 KB |
#include <iostream>
#include <set>
#include <cassert>
#include<bits/stdc++.h>
#define endl '\n'
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 = numeric_limits<ll>::max;
std::multiset < ll > left_set, right_set;
ll height;
slope_trick()
{
height = 0;
}
void add_basic(int 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)
{
assert(left_set.size() > 0);
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;
assert(right_set.size() > 0);
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 && last > 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);
}
int main()
{
speed();
solve();
return 0;
}