oj.uz

Submission #772206

# Submission time Handle Problem Language Result Execution time Memory
772206 2023-07-03T18:10:57 Z danikoynov Potatoes and fertilizers (LMIO19_bulves) C++14
20 / 100
 106 ms 26372 KB 
#include <iostream>
#include <set> 
#include <cassert>

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

const int BUFF_SIZE = 1e6;
int buffPos = BUFF_SIZE - 1;
char buff[BUFF_SIZE];

void readChar()
{
    if (++buffPos == BUFF_SIZE) fread(buff, BUFF_SIZE, 1, stdin), buffPos = 0;
}

void readInt(int &num)
{
    num = 0;
    for (; '0' > buff[buffPos] || buff[buffPos] > '9' ; readChar());
    for (; '0' <= buff[buffPos] && buff[buffPos] <= '9' ; readChar())
        num = 10 * num + buff[buffPos] - '0';
}

struct slope_trick
{
    const int inf = 1e9;
 
    std::multiset < ll > left_set, right_set;
    ll height;
 
    slope_trick()
    {
        height = 0;
    }
 
    void add_basic(int v) /// adds |x - v|
    {
        ll left = -inf;
        ll right = inf;
        if (!left_set.empty())
            left = *left_set.rbegin();
        if (!right_set.empty())
            right = *right_set.begin();
 
 
        if (v >= left && v <= right) /// function on base
        {
            left_set.insert(v);
            right_set.insert(v);
        }
        else
        if (v < left)
        {
            assert(left_set.size() > 0);
            if (left_set.size() > 0)
                left_set.erase(left_set.find(left));
            right_set.insert(left);
 
            left_set.insert(v);
            left_set.insert(v);
            
            height = height + abs(left - v);
        }
        else
        if (v > right)
        {
            ///std::cout << v << " " << right << endl; 
            assert(right_set.size() > 0);
            if (right_set.size() > 0)
                right_set.erase(right_set.begin());
            left_set.insert(right);
 
            right_set.insert(v);
            right_set.insert(v);
 
            height = height + abs(right - v);
        }
    }
 
 
    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;
    }
 
    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 prefix_minimum()
    {
        while(left_set.size() > 0)
        {       
            ll val = *left_set.begin();
            if (val >= 0)
                break;
                assert(left_set.size() > 0);
            left_set.erase(left_set.find(val));
        }
 
        ll slope = 0, base = height, last = get_right();
        
        while (get_right() <= 0)
        {
            ll distance = get_right() - last;
            base = base + distance * slope;
            slope ++;
            last = last + distance;
            assert(right_set.size() > 0);
            right_set.erase(right_set.begin());
        }
        
        if (slope != 0)
        {
            base = base + (- last) * slope;
            right_set.insert(0);
        }
        height = base;
 
        right_set.clear();
        ///right_set.clear();
    }
 
    ll query_vlaue(ll debit)
    {   
        ll last = get_left(), slope = 0, base = height;
        while(left_set.size() > 0 && last > debit)
        {
            ll distance = last - get_left();
            base = base + distance * slope;
            slope ++;
            last = last - distance;
            assert(left_set.size() > 0);
            left_set.erase(left_set.find(*left_set.rbegin()));
        }

        if (slope != 0)
        {
            base = base + (last - debit) * slope;
        }
 
        return base;
    }
};
 
 
const int maxn = 500010;
 
int n;
int a[maxn], b[maxn];
ll x[maxn], pref[maxn];
 
void solve()
{
    readInt(n);
    for (int i = 1; i <= n; i ++)
    {
        readInt(a[i]);
        readInt(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 ++)
    {
        st.add_basic(pref[i]);
        st.prefix_minimum();
        //std::cout << "--------------------" << endl;
        //st.print_slope_trick();
    }
    ///std::cout << "dasdas" << endl;
    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);
}
 
int main()
{
    speed();
    solve();
    return 0;
}

Compilation message

bulves.cpp: In member function 'void slope_trick::print_slope_trick()':
bulves.cpp:86:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   86 |         for (int cor : left_set)
      |         ^~~
bulves.cpp:88:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   88 |             std::cout << endl;
      |             ^~~
bulves.cpp: In function 'void readChar()':
bulves.cpp:15:38: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     if (++buffPos == BUFF_SIZE) fread(buff, BUFF_SIZE, 1, stdin), buffPos = 0;
      |                                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 13 ms 2804 KB Output is correct
5 Correct 29 ms 5464 KB Output is correct
6 Correct 106 ms 18608 KB Output is correct
7 Correct 83 ms 14444 KB Output is correct
8 Runtime error 35 ms 26372 KB Execution killed with signal 6
9 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 13 ms 2804 KB Output is correct
5 Correct 29 ms 5464 KB Output is correct
6 Correct 106 ms 18608 KB Output is correct
7 Correct 83 ms 14444 KB Output is correct
8 Runtime error 35 ms 26372 KB Execution killed with signal 6
9 Halted 0 ms 0 KB -

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 468 KB Output is correct
3 Correct 0 ms 340 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 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Runtime error 1 ms 852 KB Execution killed with signal 6
17 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 13 ms 2804 KB Output is correct
12 Correct 29 ms 5464 KB Output is correct
13 Correct 106 ms 18608 KB Output is correct
14 Correct 83 ms 14444 KB Output is correct
15 Runtime error 35 ms 26372 KB Execution killed with signal 6
16 Halted 0 ms 0 KB -