Submission #46384397

---

Source Code Expand

// TimaDegt <3 :flag_sk:

#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
typedef long double ld;
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> x(n), y(n);
    for (int i = 0; i < n; i++) cin >> x[i];
    for (int i = 0; i < n; i++) cin >> y[i];
    int mx = x[n-1] + 1;
    set<pair<int, int> > zac;
    zac.insert({ -mx, y[0] });
    int ans = mx;
    for (int i = 0; i + 1 < n; i++)
    {
        if (y[i] < y[i + 1]) // pribudnu zaciatky
        {
            zac.insert({ x[i] + 1, y[i + 1] - y[i] });
        }
        if (y[i] > y[i + 1])
        {
            int k = y[i] - y[i + 1], r = x[i + 1] - 1;
            while (k)
            {
                pair<int, int> p = *zac.begin();
                zac.erase(p);
                ans = min(ans, r - p.first);
                int x = min(p.second, k);
                k -= x, p.second -= x;
                if (p.second) zac.insert(p);
            }
        }
    }
    cout << (ans == mx ? -1 : ans) << "\n";
    return 0;
}

Submission Info

Judge Result