Submission #1306069

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306069		syanvu	Bikeparking (EGOI24_bikeparking)	C++20	25 / 100	461 ms	26252 KiB

Main

#include <bits/stdc++.h>

#define pb push_back
#define SS ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
#define int long long
#define all(v) v.begin(),v.end()
using namespace std;

const int N = 3e5 + 1, inf = 1e9 + 1, mod = 998244353;

int t[4 * N], add[4 * N];

void push(int v, int tl, int tr){
    t[v] = max(0ll, t[v] + add[v]);
    if(tl < tr){
        add[v * 2] += add[v];
        add[v * 2 + 1] += add[v];
    }
    add[v] = 0;
}
void upd(int v, int tl, int tr, int l, int r, int x){
    if(tl > r || l > tr) return;
    if(tl >= l && r >= tr){
        add[v] += x;
        push(v, tl, tr);
        return;
    }
    int mid = (tl + tr) / 2;
    upd(v * 2, tl, mid, l, r, x);
    upd(v * 2 + 1, mid + 1, tr, l, r, x);
    t[v] = t[v * 2] + t[v * 2 + 1];
}
int get(int v, int tl, int tr, int l, int r){
    push(v, tl, tr);
    if(tl > r || l > tr) return 0ll;
    if(tl >= l && r >= tr) return t[v];
    int mid = (tl + tr) / 2;
    return get(v * 2, tl, mid, l, r) + get(v * 2 + 1, mid + 1, tr, l, r);
}

void solve(){
    int n;
    cin >> n;
    int y[n + 1];
    pair<int, int> x[n + 1];
    for(int i = 1; i <= n; i++){
        cin >> x[i].first;
        x[i].second = i;
    }    
    for(int i = 1; i <= n; i++){
        cin >> y[i];
        upd(1, 1, n, i, i, y[i]);
    }
    sort(x + 1, x + n + 1);
    reverse(x + 1, x + n + 1);
    int p[n + 1];
    for(int i = 1; i <= n; i++) p[x[i].second] = i;
    int ans = 0;
    for(int i = 1; i <= n; i++){
        int it = x[i].second;
        int l = it + 1, r = n;
        int res = 0;
        while(l <= r){
            int mid = (l + r) / 2;
            if(get(1, 1, n, mid, it - 1) >= x[i].first){
                r = mid - 1;
            }
            else{
                res = mid;
                l = mid + 1;
            }
        }
        if(res){
            int sum = get(1, 1, n, it + 1, res);
            ans += sum;
            upd(1, 1, n, it + 1, res, -x[i].first);
            x[i].first -= sum;
            res++;
            if(res > n) continue;
            sum = get(1, 1, n, res, res);
            ans += min(sum, x[i].first);
            upd(1, 1, n, res, res, -x[i].first);
            x[i].first -= sum;
        }
    }
    for(int i = 1; i <= n; i++) y[i] = get(1, 1, n, i, i);
    for(int i = 1; i <= n; i++){
        if(y[i]){
            int inc = min(y[i], x[p[i]].first);
            y[i] -= inc;
            x[p[i]].first -= inc;
        }
        ans -= y[i];
    }
    cout << ans;
}
signed main(){ 
    SS
    // freopen("trains.in", "r", stdin);
    // freopen("trains.out", "w", stdout);
    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
}

• Subtask 1: 16 / 16
• Subtask 2: 9 / 9
• Subtask 3: 0 / 19
• Subtask 4: 0 / 24
• Subtask 5: 0 / 32