Submission #1305199

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305199		dorkikann	Potatoes and fertilizers (LMIO19_bulves)	C++20	0 / 100	1 ms	576 KiB

bulves

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

const int N = 5e5 + 5;

ll T[N];

ll Solve(int n)
{
    multiset<ll> Left, Right;
    ll level = 0;

    ll offsetL = 0, offsetR = 0;
    Left.insert(0);
    Right.insert(0);

    if(T[0] < 0) {
        offsetL += T[0];
        offsetR += T[0];
    } else 
        offsetR += T[0];

    for(int i = 1; i < n; i++) {
        ll a = 0 - offsetL;
        ll b = 0 - offsetR;

        if(Left.empty()) {
            if(b < *Right.begin()) {
                level += (*Right.begin() - b);
                Right.insert(*Right.begin());
            } else {
                if(b <= *(--Right.end())) {
                    Right.insert(b);
                    Right.insert(b);
                }
                
                Left.insert(*Right.begin() + offsetR - offsetL);
                level += (b - *Right.begin());
                Right.erase(Right.begin());
            }
        } else if(Right.empty()) {
            if(a > *(--Left.end())) {
                level += (a - *(--Left.end()));
                Left.insert(*(--Left.end()));
            } else {
                if(a >= *Left.begin()) {
                    Left.insert(a);
                    Left.insert(a);
                }
                
                Right.insert(*(--Left.end()) + offsetL - offsetR);
                level += (*(--Left.end()) - a);
                Left.erase(--Left.end());
            }
        } else {
            if(a >= *(--Left.end()) && b <= *Right.begin()) {
                Left.insert(a);
                Right.insert(b);
            } else if(a < *(--Left.end())) {
                if(a >= *Left.begin()) {
                    Left.insert(a);
                    Left.insert(a);
                }
                
                Right.insert(*(--Left.end()) + offsetL - offsetR);
                level += (*(--Left.end()) - a);
                Left.erase(--Left.end());
            } else {
                if(b <= *(--Right.end())) {
                    Right.insert(b);
                    Right.insert(b);
                }
                
                Left.insert(*Right.begin() + offsetR - offsetL);
                level += (b - *Right.begin());
                Right.erase(Right.begin());
            }
        }

        if(T[i] < 0) {
            offsetL += T[i];
            offsetR += T[i];
        } else 
            offsetR += T[i];
    }

    if(Right.empty())
        return level;
    
    ll val = level;
    ll slope = 0;
    ll last = 0;

    for(auto e : Right) {
        ll pos = e + offsetR;
        val += (pos - last) * slope;

        if(pos >= 0)
            return val - pos*slope;

        slope++;
        last = pos;
    }
    return -1;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, a, b;
    cin >> n;

    for(int i = 0; i < n; i++) {
        cin >> a >> b;
        T[i] = a - b;
    }

    cout << Solve(n) << "\n";
    return 0;
}

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