Submission #478522

#	Time	Username	Problem	Language	Result	Execution time	Memory
478522		4ndrelus	Potatoes and fertilizers (LMIO19_bulves)	C++17	0 / 100	1 ms	332 KiB

bulves

#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<LL> a, b;

void Input()
{
    cin >> n; a = vector<LL>(n); b = vector<LL>(n);
    forx(i, 0, n)
        cin >> a[i] >> b[i];
}

void Solve()
{
    vector<LL> x(n+1, 0);
    forx(i, 0, n)
        x[i+1] = a[i] - b[i] + x[i];
    echo(x);
    /*auto x = a;
    forx(i, 0, n)x[i] -= i;
    x.insert(x.begin(), 0);*/
    

    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];
    }
    priority_queue<LL> pq; LL b = 0;
    forx(i, 1, n + 1) {
        pq.push(x[i]);
        pq.push(x[i]);
        b += pq.top() - x[i];
        pq.pop();
    }

    LL a = 0;
    while (x[n] < pq.top()) {
        a -= 1;
        b += pq.top();
        pq.pop();
    }
    
    cout << b+adjust << "\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!
    }
};

• Subtask 1: 0 / 24
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 10
• Subtask 5: 0 / 36