oj.uz

Submission #772261

# Submission time Handle Problem Language Result Execution time Memory
772261 2023-07-03T20:41:05 Z radoslav11 Potatoes and fertilizers (LMIO19_bulves) C++17
100 / 100
 277 ms 40180 KB 
#include <bits/stdc++.h>
#define endl '\n'

typedef long long ll;

using namespace std;

struct slope_trick {
    const ll inf = 9223372036854775807ll;

    std::multiset < ll > left_set, right_set;
    ll height;

    slope_trick() {
        height = 0;
    }

    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 add_basic(ll v) {
        ll left = get_left(), right = get_right();

        if (v >= left && v <= right) {
            left_set.insert(v);
            right_set.insert(v);
        }
        else {
            if (v < left) {
                left_set.insert(v);
                left_set.insert(v);

                right_set.insert(left);
                left_set.erase(left_set.find(left));

                height = height + abs(v - left);
            }
            else {
                assert(false);
            }
        }
    }

    void prefix_minimum() {
        right_set.clear();
    }

    ll query_vlaue(ll debit) {
        ll last = get_left(), slope = 0, base = height;
        while(left_set.size() > 0 && get_left() > debit) {
            base = base + (last - get_left()) * slope;
            slope++;

            last = get_left();
            left_set.erase(left_set.find(last));
        }

        if (slope != 0) {
            base = base + (last - debit) * slope;
        }

        return base;
    }
};

const int maxn = 500010;

int n;
ll a[maxn], b[maxn];
ll x[maxn], pref[maxn];

void solve() {
    std::cin >> n;
    pref[0] = 0;
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i] >> 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++) {
        if (pref[i] < 0) {
            st.height += -pref[i];
            st.add_basic(0);
        }
        else {
            st.add_basic(pref[i]);
        }
        st.prefix_minimum();
    }

    ll ans = st.query_vlaue(pref[n]);
    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;
}

Subtask #1
24.0 / 24.0

# 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 540 KB Output is correct
4 Correct 19 ms 4372 KB Output is correct
5 Correct 42 ms 8500 KB Output is correct
6 Correct 147 ms 20432 KB Output is correct
7 Correct 191 ms 40180 KB Output is correct
8 Correct 218 ms 39964 KB Output is correct
9 Correct 192 ms 39524 KB Output is correct
10 Correct 246 ms 39456 KB Output is correct
11 Correct 214 ms 39508 KB Output is correct

Subtask #2
10.0 / 10.0

# 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 540 KB Output is correct
4 Correct 19 ms 4372 KB Output is correct
5 Correct 42 ms 8500 KB Output is correct
6 Correct 147 ms 20432 KB Output is correct
7 Correct 191 ms 40180 KB Output is correct
8 Correct 218 ms 39964 KB Output is correct
9 Correct 192 ms 39524 KB Output is correct
10 Correct 246 ms 39456 KB Output is correct
11 Correct 214 ms 39508 KB Output is correct
12 Correct 64 ms 10276 KB Output is correct
13 Correct 175 ms 24044 KB Output is correct
14 Correct 192 ms 39552 KB Output is correct
15 Correct 209 ms 39500 KB Output is correct
16 Correct 272 ms 39548 KB Output is correct
17 Correct 166 ms 39544 KB Output is correct
18 Correct 1 ms 596 KB Output is correct

Subtask #3
20.0 / 20.0

# 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 596 KB Output is correct
4 Correct 1 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 2 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 596 KB Output is correct

Subtask #4
10.0 / 10.0

# 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 540 KB Output is correct
4 Correct 1 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 2 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 2 ms 600 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 2 ms 596 KB Output is correct

Subtask #5
36.0 / 36.0

# 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 540 KB Output is correct
4 Correct 1 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 2 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 19 ms 4372 KB Output is correct
12 Correct 42 ms 8500 KB Output is correct
13 Correct 147 ms 20432 KB Output is correct
14 Correct 191 ms 40180 KB Output is correct
15 Correct 218 ms 39964 KB Output is correct
16 Correct 192 ms 39524 KB Output is correct
17 Correct 246 ms 39456 KB Output is correct
18 Correct 214 ms 39508 KB Output is correct
19 Correct 64 ms 10276 KB Output is correct
20 Correct 175 ms 24044 KB Output is correct
21 Correct 192 ms 39552 KB Output is correct
22 Correct 209 ms 39500 KB Output is correct
23 Correct 272 ms 39548 KB Output is correct
24 Correct 166 ms 39544 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 2 ms 600 KB Output is correct
27 Correct 1 ms 596 KB Output is correct
28 Correct 2 ms 596 KB Output is correct
29 Correct 1 ms 604 KB Output is correct
30 Correct 1 ms 596 KB Output is correct
31 Correct 2 ms 596 KB Output is correct
32 Correct 1 ms 596 KB Output is correct
33 Correct 58 ms 10172 KB Output is correct
34 Correct 130 ms 23948 KB Output is correct
35 Correct 243 ms 39572 KB Output is correct
36 Correct 277 ms 39580 KB Output is correct
37 Correct 209 ms 39536 KB Output is correct
38 Correct 218 ms 39628 KB Output is correct
39 Correct 199 ms 39548 KB Output is correct
40 Correct 162 ms 35892 KB Output is correct
41 Correct 197 ms 39500 KB Output is correct
42 Correct 204 ms 39660 KB Output is correct
43 Correct 190 ms 39536 KB Output is correct
44 Correct 200 ms 39468 KB Output is correct
45 Correct 254 ms 39464 KB Output is correct
46 Correct 144 ms 39496 KB Output is correct
47 Correct 148 ms 30896 KB Output is correct