제출 #772247

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
772247		danikoynov	Potatoes and fertilizers (LMIO19_bulves)	C++14	30 / 100	187 ms	39440 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;
        
        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;
        assert(st.left_set.size() == cnt);
        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();
        solve();
        return 0;
    }

컴파일 시 표준 에러 (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;
      |                 ^~~
In file included from /usr/include/c++/10/cassert:44,
                 from bulves.cpp:3:
bulves.cpp: In function 'void solve()':
bulves.cpp:145:35: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
  145 |         assert(st.left_set.size() == cnt);
      |                ~~~~~~~~~~~~~~~~~~~^~~~~~

• Subtask 1: 0 / 24
• Subtask 2: 0 / 10
• Subtask 3: 20 / 20
• Subtask 4: 10 / 10
• Subtask 5: 0 / 36