oj.uz

답안 #478521

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
478521 2021-10-07T20:59:32 Z 4ndrelus Potatoes and fertilizers (LMIO19_bulves) C++17
24 / 100
 127 ms 17856 KB 
#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();
    }
    b = 0;
    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
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 10 ms 2384 KB Output is correct
5 Correct 21 ms 4456 KB Output is correct
6 Correct 55 ms 9964 KB Output is correct
7 Correct 127 ms 17856 KB Output is correct
8 Correct 106 ms 17852 KB Output is correct
9 Correct 108 ms 17852 KB Output is correct
10 Correct 91 ms 17836 KB Output is correct
11 Correct 92 ms 17852 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 10 ms 2384 KB Output is correct
5 Correct 21 ms 4456 KB Output is correct
6 Correct 55 ms 9964 KB Output is correct
7 Correct 127 ms 17856 KB Output is correct
8 Correct 106 ms 17852 KB Output is correct
9 Correct 108 ms 17852 KB Output is correct
10 Correct 91 ms 17836 KB Output is correct
11 Correct 92 ms 17852 KB Output is correct
12 Incorrect 28 ms 5984 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 0 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Incorrect 0 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Incorrect 0 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -