Submission

Score: 100

User: tHeNyXs

Problemset: Red Zone

Language: cpp

Time: 0.048 second

Submitted On: 2026-03-05 16:18:12

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

struct SegTree {
    int n;
    vector<long long> tree, lazy;

    SegTree(int n) {
        this->n = n;
        tree.resize(4*n);
        lazy.resize(4*n);
    }

    void build(int node, int l, int r, vector<int>& a) {
        if (l == r) {
            tree[node] = a[l];
            return;
        }
        int mid = (l+r)/2;
        build(node*2,l,mid,a);
        build(node*2+1,mid+1,r,a);
        tree[node] = max(tree[node*2], tree[node*2+1]);
    }

    void push(int node) {
        if (lazy[node]) {
            for (int child:{node*2,node*2+1}) {
                tree[child] += lazy[node];
                lazy[child] += lazy[node];
            }
            lazy[node] = 0;
        }
    }

    void update(int node,int l,int r,int ql,int qr,long long val){
        if (qr<l || r<ql) return;

        if (ql<=l && r<=qr){
            tree[node]+=val;
            lazy[node]+=val;
            return;
        }

        push(node);

        int mid=(l+r)/2;

        update(node*2,l,mid,ql,qr,val);
        update(node*2+1,mid+1,r,ql,qr,val);

        tree[node]=max(tree[node*2],tree[node*2+1]);
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n,m,l,d;
    cin>>n>>m>>l>>d;

    vector<int>a(n+1);

    for(int i=1;i<=n;i++) cin>>a[i];

    SegTree seg(n);
    seg.build(1,1,n,a);

    int ans=-1;

    for(int i=1;i<=m;i++){
        int pos; cin>>pos;

        if(ans!=-1) continue;

        int L=max(1,pos-l);
        int R=min(n,pos+l);

        seg.update(1,1,n,L,R,-d);

        if(seg.tree[1]<=0) ans=i;
    }

    cout<<ans;
}