Submission #1343295

#TimeUsernameProblemLanguageResultExecution timeMemory
1343295coin_Bikeparking (EGOI24_bikeparking)C++20
68 / 100
1006 ms21556 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), y(n+1);
    for (int i = 1; i <= n; i++){
        cin >> x[i];
    }
    for (int i = 1; i <= n; i++){
        cin >> y[i];
    }
    build(1, 1, n, x);
    // need to fix nlog^2n
    int ans = 0;
    for (int i = 2; i <= n; i++){
        // put at next availible slot
        int chck = get(1, 1, n, 1, i-1);
        if (chck <= y[i]){
            update(1, 1, n, 1, i-1, 0);
            y[i] -= chck;
            ans += chck;
        }
        else{
            int l = 1, r = i-1;
            while(l < r){
                int mid = (l + r + 1) >> 1;
                int tot = get(1, 1, n, mid, i-1);
                if (tot >= y[i]){
                    l = mid;
                }
                else{
                    r = mid - 1;
                }
            }
            // l is the one that is not 0
            if (l != i-1){
                int rem1 = y[i] - get(1, 1, n, l+1, i-1);
                int rem = get(1, 1, n, l, l) - rem1;
                update(1, 1, n, l+1, i-1, 0);
                update(1, 1, n, l, l, rem);
            }
            else{
                int rem = get(1, 1, n, i-1, i-1) - y[i];
                update(1, 1, n, i-1, i-1, rem);
            }
            ans += y[i];
            y[i] = 0;
        }
    }
    for (int i = 1; i <= n; i++){
        // though no more spots but might speed up st
        x[i] = get(1, 1, n, 1, i);
        int fit = min(x[i], y[i]);
        ans -= y[i] - fit;
    }
    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...