oj.uz

Submission #772254

# Submission time Handle Problem Language Result Execution time Memory
772254 2023-07-03T20:27:26 Z danikoynov Potatoes and fertilizers (LMIO19_bulves) C++14
30 / 100
 367 ms 39416 KB 
#include <iostream>
#include<stdio.h>
#include<cmath>
#include <set>
#include <cassert>
#include <numeric>
#include <fstream>

#define endl '\n'
#define int long long
typedef long long ll;

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) /// adds |x - 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);
        }
    }


    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;
    }


    void prefix_minimum()
    {


        right_set.clear();
        ///right_set.clear();
    }

    ll query_vlaue(ll debit)
    {

        ll last = get_left(), slope = 0, base = height;
        while(left_set.size() > 0 && get_left() > debit)
        {
            ll distance = last - get_left();
            base = base + distance * slope;
            slope ++;
            last = last - distance;
            assert(left_set.size() > 0);
            left_set.erase(prev(left_set.end()));
        }

        if (slope != 0)
        {
            assert(last >= debit);
            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;
    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];
    }


    ll sum = 0;
    for (int i = 1; i <= n; i ++)
    {
        sum += abs(pref[i]);
    }
    slope_trick st;

    ll cnt = 0;
    for (int i = 1; i <= n; i ++)
    {
        if (pref[i] < 0)
        {
            st.height += -pref[i];
            cnt ++;
            st.add_basic(0);
        }
        else
            st.add_basic(pref[i]), cnt ++;
        st.prefix_minimum();
        //std::cout << "--------------------" << endl;
        // st.print_slope_trick();
    }
    ///std::cout << "dasdas" << endl;

    ll sumf = 0;
    for (ll val : st.left_set)
        sumf += val;
    sumf += st.height;

    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);
}

signed main()
{

    ///speed();
    ///freopen("test.txt","r", stdin);

    solve();

    return 0;
}

Subtask #1
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 3 ms 492 KB Output is correct
4 Correct 32 ms 4120 KB Output is correct
5 Correct 63 ms 8128 KB Output is correct
6 Correct 195 ms 19788 KB Output is correct
7 Correct 367 ms 39300 KB Output is correct
8 Incorrect 366 ms 39416 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 3 ms 492 KB Output is correct
4 Correct 32 ms 4120 KB Output is correct
5 Correct 63 ms 8128 KB Output is correct
6 Correct 195 ms 19788 KB Output is correct
7 Correct 367 ms 39300 KB Output is correct
8 Incorrect 366 ms 39416 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 412 KB Output is correct
5 Correct 1 ms 436 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 3 ms 544 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 3 ms 492 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 412 KB Output is correct
6 Correct 1 ms 436 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 3 ms 544 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 2 ms 468 KB Output is correct
14 Correct 2 ms 468 KB Output is correct
15 Correct 2 ms 488 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 2 ms 468 KB Output is correct
18 Correct 2 ms 468 KB Output is correct

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 3 ms 492 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 412 KB Output is correct
6 Correct 1 ms 436 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 3 ms 544 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 32 ms 4120 KB Output is correct
12 Correct 63 ms 8128 KB Output is correct
13 Correct 195 ms 19788 KB Output is correct
14 Correct 367 ms 39300 KB Output is correct
15 Incorrect 366 ms 39416 KB Output isn't correct
16 Halted 0 ms 0 KB -