Submission

Score: 100

User: Kittiponn

Problemset: Red Zone

Language: cpp

Time: 0.022 second

Submitted On: 2026-03-05 21:10:34

#include <bits/stdc++.h>
#define ll long long
#define sp << ' ' <<
#define nl << '\n' 
#define cnl cout << '\n'
using namespace std;
const int nx = 1e5+5;
const int INF = 1e9+5;
const int MOD = 1e9+7;
ll n,m,l,d;
ll ho[nx],bo[nx];
ll da[nx], pr[nx];
int solve(ll md){
    for(int i = 0 ;i <= n;i++)da[i] = 0,pr[i] = 0;
    for(int i = 1;i <= md;i++){
        ll lf = max((ll)1,bo[i]-l);
        ll ri = min(n+1,bo[i]+l+1);
        pr[lf] += d;
        pr[ri] -= d;
    }
    for(int i = 1 ;i <= n;i++){
        da[i] = da[i-1]+pr[i];
    }
    for(int i = 1 ;i <= n;i++){
        if(ho[i] - da[i] > 0)return 0;
    }
    return 1;
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m >> l >> d;
    for(int i = 1 ;i <= n;i++)cin >> ho[i];
    for(int i = 1 ;i <= m;i++)cin >> bo[i];
    ll lo = 1,hi = m+1;
    while(lo < hi){
        ll md = (lo+hi)/2;
        if(solve(md))hi = md;
        else lo = md + 1;
    }
    if(lo == m+ 1)cout << "-1";
    else cout << lo;

}