oj.uz

Submission #772170

# Submission time Handle Problem Language Result Execution time Memory
772170 2023-07-03T17:35:35 Z danikoynov Potatoes and fertilizers (LMIO19_bulves) C++14
20 / 100
 1000 ms 19592 KB 
#include <iostream>
#include <set> 
#define endl '\n'
 
typedef long long ll;
 
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)
        {
            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; 
            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)
        {
            int val = *left_set.begin();
            if (val >= 0)
                break;
            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;
            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(last > debit)
        {
            ll distance = last - get_left();
            base = base + distance * slope;
            slope ++;
            last = last - distance;
            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;
ll a[maxn], b[maxn], 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];
    }
 
    
    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:63:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   63 |         for (int cor : left_set)
      |         ^~~
bulves.cpp:65:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   65 |             std::cout << endl;
      |             ^~~

Subtask #1
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 15 ms 2884 KB Output is correct
5 Correct 34 ms 5580 KB Output is correct
6 Correct 121 ms 19592 KB Output is correct
7 Correct 116 ms 17380 KB Output is correct
8 Execution timed out 1098 ms 15948 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 15 ms 2884 KB Output is correct
5 Correct 34 ms 5580 KB Output is correct
6 Correct 121 ms 19592 KB Output is correct
7 Correct 116 ms 17380 KB Output is correct
8 Execution timed out 1098 ms 15948 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 2 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 484 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 0 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 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 2 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 484 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 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 1 ms 468 KB Output is correct
16 Execution timed out 1089 ms 468 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 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 2 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 484 KB Output is correct
11 Correct 15 ms 2884 KB Output is correct
12 Correct 34 ms 5580 KB Output is correct
13 Correct 121 ms 19592 KB Output is correct
14 Correct 116 ms 17380 KB Output is correct
15 Execution timed out 1098 ms 15948 KB Time limit exceeded
16 Halted 0 ms 0 KB -