Submission

Score: 100

User: mydKN

Problemset: Red Zone

Language: cpp

Time: 0.024 second

Submitted On: 2026-03-19 22:52:28

#include <bits/stdc++.h>

using namespace std;

#define pii pair<int, int>
#define F first
#define S second

const int maxn = 1e5 + 5;

int n, m, l, d;
int arr[maxn];
pii bomb[maxn];
int lo, hi, res = -1;
int del[maxn];

bool ok(int mid){
	memset(del, 0, sizeof(del));
	for(int i=1;i<=mid;++i){
		del[bomb[i].F] += d;
		del[bomb[i].S] -= d;
	}
	for(int i=1;i<=n;++i){
		del[i] += del[i-1];
		if(del[i] < arr[i]){
			return 0;
		}
	}
	return 1;
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin >> n >> m >> l >> d;
	for(int i=1;i<=n;++i){
		cin >> arr[i];
	}
	for(int i=1;i<=m;++i){
		int x;
		cin >> x;
		bomb[i].F = max(1, x - l);
		bomb[i].S = min(n, x + l) + 1;
	}
	lo = 1, hi = m;
	while(lo <= hi){
		int mid = lo + (hi - lo) / 2;
		if(ok(mid)){
			res = mid;
			hi = mid - 1;
		}
		else lo = mid + 1;
	}
	cout << res;
}