Submission

Score: 100

User: njoop

Problemset: Red Zone

Language: cpp

Time: 0.021 second

Submitted On: 2025-04-11 13:01:37

#include <bits/stdc++.h>
#define int long long
using namespace std;

int n, m, l, d, arr[100010], bomb[100010], sw[100010];

bool solve(int cnt) {
    for(int i=0; i<=n+1; i++) {
        sw[i] = 0;
    }
    for(int i=1; i<=min(cnt, m); i++) {
        sw[max(0LL, bomb[i]-l)]++;
        sw[min(n+1, bomb[i]+l+1)]--;
    }
    int dur=0;
    for(int i=0; i<=n; i++) {
        dur += sw[i];
        sw[i] = dur*d;
    }
    for(int i=1; i<=n; i++) {
        if(sw[i] < arr[i]) return 0;
    }
    return 1;
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m >> l >> d;
    for(int i=1; i<=n; i++) {
        cin >> arr[i];
    }
    for(int i=1; i<=m; i++) {
        cin >> bomb[i];
    }
    int lo=1, r=m+1;
    while(lo < r) {
        int mid = (lo+r)/2;
        if(solve(mid)) {
            r = mid;
        } else {
            lo = mid+1;
        }
    }
    if(lo >= m+1) cout << -1;
    else cout << lo;
}