제출 #1343317

#제출 시각아이디문제언어결과실행 시간메모리
1343317coin_Bikeparking (EGOI24_bikeparking)C++20
28 / 100
32 ms12344 KiB
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int maxn = 3e5 + 6;
int st[4*maxn+5], lazy[4*maxn+5];
void build(int id, int l, int r, vector<int> &a){
    lazy[id] = -1;
    if (l == r){
        st[id] = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(id << 1, l, mid, a);
    build(id << 1 | 1, mid+1, r, a);
    st[id] = st[id << 1] + st[id << 1 | 1];
}

void down(int id, int l, int r){
    int mid = (l + r)/2;
    if (lazy[id] != -1){
        lazy[id << 1] = lazy[id];
        lazy[id << 1 | 1] = lazy[id];
        // set all into lazy[id]
        st[id << 1] = lazy[id]*(mid - l + 1);
        st[id << 1 | 1] = lazy[id]*(r - mid);
        lazy[id] = -1;
    }
}

int get(int id, int l, int r, int ul, int ur){
    if (l > ur || r < ul) return 0;
    if (ul <= l && r <= ur) return st[id];
    down(id, l, r);
    int mid = (l + r) >> 1;
    return get(id << 1, l, mid, ul, ur) + get(id << 1|1, mid+1, r, ul, ur);
}

void update(int id, int l, int r, int ul, int ur, int val){
    if (l > ur || r < ul) return;
    if (ul <= l && r <= ur){
        st[id] = val * (r - l + 1);
        lazy[id] = val;
        return;
    }
    down(id, l, r);
    int mid = (l + r) >> 1;
    update(id << 1, l, mid, ul, ur, val);
    update(id << 1 | 1, mid+1, r, ul, ur, val);
    st[id] = st[id << 1] + st[id << 1 | 1];
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> x(n+1, 0), y(n+1), pref(n+1, 0);
    for (int i = 1; i <= n; i++){
        cin >> x[i];
        pref[i] = x[i] + pref[i-1];
    }
    for (int i = 1; i <= n; i++){
        cin >> y[i];
    }
    int ans = 0, offset = 0;
    stack<pair<int, int>> st;
    for (int i = 2; i <= n; i++){
        st.push({i-1, x[i-1]});
        while(!st.empty() && y[i] > 0){
            pair<int, int> pa = st.top();
            st.pop();
            int num = pa.second;
            if (num > y[i]){
                st.push({pa.first, num - y[i]});
                y[i] = 0;
                ans += y[i];
                x[pa.first] = num - y[i];
            }
            else{
                y[i] -= num;
                ans += num;
                x[pa.first] = 0;
            }
        }
    }
    for (int i = 1; i <= n; i++){
        ans -= y[i] - min(x[i], y[i]);
    }
    cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...