Submission #772245

#	Time	Username	Problem	Language	Result	Execution time	Memory
772245		danikoynov	Potatoes and fertilizers (LMIO19_bulves)	C++14	0 / 100	226 ms	80188 KiB

bulves

    #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 (stderr)

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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 10
• Subtask 5: 0 / 36