oj.uz

Submission #772245

# Submission time Handle Problem Language Result Execution time Memory
772245 2023-07-03T19:55:06 Z danikoynov Potatoes and fertilizers (LMIO19_bulves) C++14
0 / 100
 226 ms 80188 KB 
    #include <iostream>
    #include <set> 
    #include <cassert>
    #include <numeric>
    #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;
        
        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();
            //std::cout << "--------------------" << endl;
            // st.print_slope_trick();
        }
        ///std::cout << "dasdas" << endl;
        ll ans = st.query_vlaue(pref[n]);
        assert(abs(ans - sum) < 10);
        ///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();
        solve();
        return 0;
    }

Compilation message

bulves.cpp: In member function 'void slope_trick::print_slope_trick()':
bulves.cpp:62:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   62 |             for (int cor : left_set)
      |             ^~~
bulves.cpp:64:17: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   64 |                 std::cout << endl;
      |                 ^~~

Subtask #1
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 18 ms 4564 KB Output is correct
5 Correct 40 ms 8632 KB Output is correct
6 Correct 108 ms 20876 KB Output is correct
7 Correct 197 ms 40652 KB Output is correct
8 Runtime error 226 ms 80188 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 296 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 18 ms 4564 KB Output is correct
5 Correct 40 ms 8632 KB Output is correct
6 Correct 108 ms 20876 KB Output is correct
7 Correct 197 ms 40652 KB Output is correct
8 Runtime error 226 ms 80188 KB Execution killed with signal 6
9 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Runtime error 2 ms 468 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Runtime error 2 ms 468 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Runtime error 2 ms 468 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -