Submission

Score: 0

User: meme_boi2

Problemset: Red Zone

Language: cpp

Time: 0.000 second

Submitted On: 2026-03-20 10:29:29

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii array<int,2>
int32_t main(){
    cin.tie(nullptr)->sync_with_stdio(0);
    int n, m, radius, d;
    cin >> n >> m >> radius >> d;
    vector<int> mat(n+1),dp(n+1,0);
    vector<pii> dd(m);
    for(int i = 1; i <= n; i++){
        cin >> mat[i];
    }
    for(int i = 0; i < m; i++){
        int x;
        cin >> x;
        dd[i] = {max(1,x-radius),min(n,x+radius)};
    }
    int l = 1, r = m,ans = -1;
    while(l <= r){
        int mid = (l+r)>>1;
        bool chk = 1;
       // cout << l<< ' ' << r << '\n';
        for(int i = 0; i < mid; i++){
            dp[dd[i][0]] += d;
            if(dd[i][1] + 1 <= n){
                dp[dd[i][1] + 1] -= d;
            }
        }
        int cur = 0;
        for(int i = 1; i <= n; i++){
            cur += dp[i];
            dp[i-1] = 0;
            if(mat[i] > cur){
             //   cout << i << ' ' << mat[i] << ' ' << cur << '\n';
                chk = 0;
            //    break;
            }
        }
        dp[n] = 0;
        if(chk){
            r = mid - 1;
            ans = mid;
        }else{
            l = mid + 1;
        }
    }
    cout << ans;
}