제출 #1369019

#제출 시각아이디문제언어결과실행 시간메모리
1369019AzeTurk810Bikeparking (EGOI24_bikeparking)C++20
100 / 100
22 ms5088 KiB
/*
Telebe of Adicto && Mamedov yani AzeTurk810
I see humans but no humanity
*/
#include <algorithm>
#include <cassert>
#include <iostream>
#include <stack>
#include <vector>

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

using ll = long long;
using namespace std;

#define ln '\n'
#define INFi 1e9
#define INFll 1e18

#ifdef ONPC
#include <algo.hpp>
#else
#define dbg(...)
#define dbg_out(...)
#define myassert(Expr, Msg) ;
#endif

template <typename T>
struct segtree {
#define lv (v << 1)
#define rv ((v << 1) | 1)
    vector<T> sum, lazy, *X;
    size_t N;
    segtree(int _n, vector<T> &Y) : N(_n), sum(N << 2, 0), lazy(N << 2, 0), X(Y) {
        ;
    };

  private:
    inline void push(int v, int l, int r) {
        if (lazy[v] == 0)
            return;
        sum[v] -= lazy[v];
        myassert(sum[v] >= 0, "WA: sum always must be greater than 0");
        if (sum[lv] - lazy[lv] <= lazy[v]) {
            lazy[lv] += lazy[v];
        } else {
            T rs = lazy[v] - sum[lv] + lazy[lv];
            lazy[lv] = sum[lv];
            lazy[rv] += rs;
        }
    }

    void build(int v, int l, int r) {
        if (l == r) {
            sum[v] = X[v];
            return;
        }
        int mid = (l + r) >> 1;
        build(lv, l, mid);
        build(rv, mid + 1, r);
        sum[v] = sum[lv] + sum[rv];
    }

    void upd(int v, int l, int r, int ql, int qr, T val) {
        push(v, l, r);
        if (ql <= l && r <= qr) {
            lazy[v] += val;
            push(v, l, r);
            return;
        }
        if (ql > r || qr < l) {
            return;
        }
        int mid = (l + r) >> 1;
        push(lv, l, mid);
        T vall = min(sum[lv], val);
        T valr = val - valr;
        upd(lv, l, mid, ql, qr, vall);
        upd(rv, mid + 1, r, ql, qr, valr);
        sum[v] = sum[lv] + sum[rv];
    }

    T ask(int v, int l, int r, int ql, int qr, T val) {
        ;
    }
};

inline void systemd() {
}

char solve() {
    size_t n;
    if (!(cin >> n))
        return 1;
    vector<int> X(n), Y(n);
    for (int &x : X)
        cin >> x;
    for (int &y : Y)
        cin >> y;
    stack<size_t> st;
    ll ans = 0;
    for (size_t i = 0; i < n; i++) {
        while (!st.empty() && Y[i] > 0) {
            size_t j = st.top();
            st.pop();
            ll x = min(X[j], Y[i]);
            X[j] -= x;
            Y[i] -= x;
            ans += x;
            if (X[j] > 0)
                st.push(j);
        }
        if (X[i] > 0)
            st.push(i);
    }
    for (size_t i = 0; i < n; i++) {
        Y[i] -= X[i];
    }
    for (size_t i = 0; i < n; i++) {
        if (Y[i] > 0) {
            ans -= Y[i];
        }
    }
    cout << ans << ln;
    systemd();
    return 0;
}

// Attack on titan<3

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    int t = 1e9;
    // cin >> t;
    for (int cases = 0; cases < t; cases++) {
        if (solve())
            break;
#ifdef ONPC
        cerr << "__________\n";
#endif
    }
}
// Just Imaginary
/*
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣀⠀⠀⠀⢀⣴⣾⠀⠀⠀⡀⢀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣿⣦⣾⣿⣿⣿⣿⣿⡆⠁⠀⢀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠹⣿⣿⣿⣿⣿⣿⣿⣿⡿⠁⠀⡠⠂⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠠⠔⠚⣿⣿⣿⣿⣿⣦⡄⠀⠁⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢀⠠⠐⢂⠉⡀⣀⣤⣄⢻⣿⣿⡟⢈⡹⣿⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⡀⠄⠂⠈⠀⣶⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠘⣷⡀⠀⡀⠐⠂⠐⢄
⠀⠀⠀⠀⠀⠀⠀⣿⣿⠟⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⣀⣾⣷⠯⠀⠤⠤⠄⠈
⠀⠀⠀⠀⠀⠀⣼⣿⡟⠀⠀⣹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⣰⣿⠋⠀⠀⢠⣾⣿⣿⣿⣿⣿⣭⠟⢻⣿⣿⣿⣿⡿⠁⠀⠀⠀⠀
⠀⠀⠀⣀⣶⡟⠁⠀⢾⣶⣿⠟⠉⠈⢻⣿⣿⣿⣦⣜⠀⠛⠛⠿⠁⠀⠀⠀⠀⠀
⠚⠻⠿⠿⡿⠁⠀⢠⣿⣿⠁⠀⣠⠖⠋⠉⠻⣿⣿⣿⣶⡀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⣰⣿⡿⠃⠠⠊⠁⠀⠀⠀⠀⠈⢿⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⢀⣴⡿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⣠⣾⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⢀⣴⠾⠟⠛⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
*/
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…