#define DEBUG 0
#define TESTSETS 0
#if DEBUG
#include <ultimate_power_2.h>
#else
#include <bits/stdc++.h>
#define echo(...) {}
#endif
/* ------- utils ------- */
#define debug if(DEBUG)
#define P2(x) (1LL<<(x))
#define st first
#define nd second
#define mt make_tuple
#define gottagofast() ios::sync_with_stdio(0); cin.tie(0);
#define band(x, y) ((x) & (y))
#define bor(x, y) ((x) | (y))
#define all(x) (x).begin(), (x).end()
#define len(x) (int)(x).size()
#define ffor(i, a, b) for(int i = (a), i##e = (b); i <= i##e; i++)
#define dfor(i, a, b) for(int i = (a), i##e = (b); i >= i##e; i--)
#define forx(i, a, b) for(int i = (a), i##e = (b); i < i##e; i++) //!!! eXclusive
#define dforx(i, a, b) for(int i = (a), i##e = (b); i > i##e; i--)//!!! eXclusive
using namespace std;
using LL = long long;
using ULL = unsigned long long;
constexpr LL INF = LLONG_MAX / 2 - 1;
constexpr int iINF = INT_MAX / 2 - 1;
LL MOD = 1'000'000'007;
int clamp(int x, int a, int b) { assert(a <= b); return min(max(x, a), b); }
template<class T> T sum(const vector<T>& vector) { return accumulate(vector.begin(), vector.end(), static_cast<T>(0)); }
template<class T> T max(const vector<T>& vector) { return *max_element(vector.begin(), vector.end()); }
template<class T> T min(const vector<T>& vector) { return *min_element(vector.begin(), vector.end()); }
template<class T> int popcnt(T x) { int c = 0; while (x > 0) c += x & 1, x >>= 1; return c; }
template<class T, class U> pair<T, U> operator+(const pair<T, U>& a, const pair<T, U>& b) { return { a.st + b.st, a.nd + b.nd }; }
vector<LL> factorize(LL x)
{
assert(x > 0);
vector<LL> f;
while (x % 2 == 0)
f.push_back(2),
x /= 2;
for (LL d = 3; d * d <= x; d += 2)
while (x % d == 0)
f.push_back(d),
x /= d;
if (x > 1)
f.push_back(x);
return f;
}
vector<pair<LL, int>> compress(vector<LL> v)
{
vector<pair<LL, int>> p;
sort(all(v));
for (int i = 0, j; i < len(v); i = j) {
for (j = i + 1; j < len(v) && v[i] == v[j]; j++);
p.emplace_back(v[i], j - i);
}
return p;
}
int randx(int a, int b) { return rand() % (b-a) + a; }//rand exclusive [a, b)
LL fpow(LL a, LL b)
{
if (b == 0) return 1;
if (b % 2 == 1) return fpow(a, b - 1) * a % MOD;
LL p = fpow(a, b / 2);
return p * p % MOD;
}
LL iceil(LL a, LL b)
{
assert(a > 0);
return (a - 1) / b + 1;
}
/* --------------------- */
int n;
vector<int> a, b;
void Input()
{
cin >> n; a = vector<int>(n); b = vector<int>(n);
forx(i, 0, n)
cin >> a[i] >> b[i];
}
struct STFunction
{
LL a = 0, b = 0;
multiset<LL> S;
static STFunction AbsVal(LL b)
{
return STFunction{ 1, -b, {b,b} };//yeeeah
}
STFunction& operator+=(const STFunction& rhs) {
S.insert(rhs.S.begin(), rhs.S.end());
a += rhs.a;
b += rhs.b;
return *this;
}
STFunction operator+(const STFunction& rhs) {
return STFunction(*this) += rhs;
}
};
void Solve()
{
vector<LL> x(n+1, 0);
forx(i, 0, n)
x[i+1] = a[i] - b[i] + x[i];
echo(x);
LL adjust = 0;
forx(i, 1, n+1) {
if (x[i] < 0)
adjust += -x[i],
x[i] = 0;
else if (x[i] > x[n])
adjust += x[i] - x[n],
x[i] = a[n-1];
}
STFunction stf;
forx(i, 1, n+1) {
stf += STFunction::AbsVal(x[i]);
auto it = prev(stf.S.end());
auto x = *it;
stf.S.erase(it);
stf.b = x + stf.b;
stf.a -= 1;
assert(stf.a == 0);
}
cout << adjust + stf.b << "\n";
}
void Brute()
{
}
int main()
{
gottagofast();
int z = 1;
#if TESTSETS
cin >> z;
#endif
forx(case_num, 0, z) {
Input();
echo(c::green, "---------------");
Solve();
echo(c::green, "---------------");
Brute();
}
}
/* ---- basically trash ---- */
struct Matrix3x3
{
array<array<int, 3>, 3> m;
Matrix3x3()
{
m[0] = { 1, 0, 0 };
m[1] = { 0, 1, 0 };
m[2] = { 0, 0, 1 };
}
Matrix3x3(const vector<vector<int>>& init)
{
forx(i, 0, 3)forx(j, 0, 3)m[i][j] = init[i][j];
}
static Matrix3x3 L90(int a, int b)
{
return Matrix3x3({ {0, -1, a + b},
{1, 0, b - a},
{0, 0, 1 } });
}
static Matrix3x3 R90(int a, int b)
{
return Matrix3x3({ {0, 1, a - b},
{-1, 0, a + b},
{0, 0, 1 } });
}
array<int, 3>& operator[](int idx) { return m[idx]; }
const array<int, 3>& operator[](int idx) const { return m[idx]; }
Matrix3x3 operator* (const Matrix3x3& other) const
{
Matrix3x3 result(vector<vector<int>>(3, vector<int>(3, 0)));//czy teraz sa same 0?
forx(i, 0, 3)
forx(j, 0, 3)
forx(k, 0, 3)
result.m[i][j] += (*this)[i][k] * other.m[k][j];
return result;
}
Matrix3x3 operator*= (const Matrix3x3& other)
{
return *this = *this * other;
}
vector<int> operator* (const vector<int>& v) const
{
assert(len(v) == 3);
vector<int> result(3, 0);
forx(i, 0, 3)
forx(j, 0, 3)
result[i] += m[i][j] * v[j];
return result;
}
};
struct Tree
{
int LC;
vector<Matrix3x3> tree;
Tree(int n) : LC(max(4, 1 << ((int)log2(n) + 1))), tree(2 * LC) {}
Matrix3x3 Query(int i)//
{
return Query(1, 0, i + 1, 0, LC);
}
Matrix3x3 Query(int v, int a, int b, int ta, int tb)
{
if (not(a < b)) return Matrix3x3();
if (a == ta && tb == b) return tree[v];
int tm = (ta + tb) / 2;
auto m1 = Query(2 * v, a, min(tm, b), ta, tm);
auto m2 = Query(2 * v + 1, max(tm, a), b, tm, tb);
return m1 * m2;
}
void Update(int i, const Matrix3x3& rotation)
{
int v = i + LC;
tree[v] *= rotation;
while (v /= 2)
//tree[v] *= rotation;
tree[v] = tree[2 * v] * tree[2 * v + 1];//kolejnosc!
}
};
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
2 ms |
460 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
460 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
2 ms |
460 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
460 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
2 ms |
460 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
2 ms |
460 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
460 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
2 ms |
460 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
460 KB |
Output isn't correct |
