Submission

Score: 100

User: erng

Problemset: Red Zone

Language: cpp

Time: 0.020 second

Submitted On: 2026-02-14 21:22:19

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const ll nx=1e5+5;

ll n, m, L, arr[nx], cnt, a, bo[nx], l=1, r, md, add[nx], sub[nx], cu[nx], b,k, d;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m>>L>>d;
    for (int i=1; i<=n; i++) cin>>arr[i];
    for (int i=1; i<=m; i++)
    {
        cin>>bo[i];
    }
    r=m+1;
    l=1;
    while (l<r)
    {
        md=(l+r)/2;
        k=0;
        b=0;
        for (int i=1; i<=n; i++) cu[i]=0, add[i]=0, sub[i]=0;
        for (int i=1; i<=md;i++)
        {
            add[max(bo[i]-L, 1ll)]+=d;
            sub[min(bo[i]+L, n)]+=d;
        }
        // for (int i=1; i<=n; i++) cout<<md<<" : "<<add[i]<<" "<<sub[i]<<'\n';
        for (int i=1; i<=n; i++)
        {
            b+=add[i];
            cu[i]=b;
            b-=sub[i];
        }
        for (int i=1; i<=n; i++)
        {
            if (cu[i]<arr[i]) 
            {
                k=1;
                break;
            }
        }
        if (!k) r=md;
        else l=md+1;
    }
    if (l==m+1) cout<<-1;
    else cout<<l;
}