Submission

Score: 100

User: foldnut

Problemset: Red Zone

Language: cpp

Time: 0.377 second

Submitted On: 2025-12-01 18:34:36

#include <bits/stdc++.h>
using namespace std;
const int N = 111111;
int n, m, len, d, a[N], b[N];
struct segtree{
    int seg[4 * N], lazy[4 * N];
    void build(int nd, int l, int r){
        if(l == r) return seg[nd] = 0, lazy[nd] = 0, void();
        int md = (l + r) / 2;
        build(nd * 2, l, md);
        build(nd * 2 + 1, md + 1, r);
    }
    void push(int nd, int l, int r){
        if(lazy[nd] != 0){
            seg[nd] += (r - l + 1) * lazy[nd];
            if(l != r){
                lazy[nd * 2] += lazy[nd];
                lazy[nd * 2 + 1] += lazy[nd];
            }
            lazy[nd] = 0;
        }
    }
    void upd(int nd, int l, int r, int ql, int qr, int x){
        if(r < ql || qr < l) return;
        if(ql <= l && r <= qr) return lazy[nd] += x, push(nd, l, r), void();
        int md = (l + r) / 2;
        upd(nd * 2, l, md, ql, qr, x);
        upd(nd * 2 + 1, md + 1, r, ql, qr, x);
        seg[nd] = seg[nd * 2] + seg[nd * 2 + 1];
    }
    int qry(int nd, int l, int r, int pos){
        push(nd, l, r);
        if(l == r) return seg[nd];
        int md = (l + r) / 2;
        if(pos <= md) return qry(nd * 2, l, md, pos);
        else return qry(nd * 2 + 1, md + 1, r, pos);
    }
}s;
bool ok(int x){
    s.build(1, 1, n);
    for(int i = 1;i<=x;i++) s.upd(1, 1, n, max(1, b[i] - len), min(n, b[i] + len), d);
    bool f = 1;
    for(int i = 1;i<=n;i++) if(s.qry(1, 1, n, i) < a[i]) f = 0;
    return f;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m >> len >> d;
    for(int i = 1;i<=n;i++) cin >> a[i];
    for(int i = 1;i<=m;i++) cin >> b[i];
    int l = 1, r = m, ans = -1;
    while(l <= r){
        int md = (l + r) / 2;
        if(ok(md)){
            ans = md;
            r = md - 1;
        }else{
            l = md + 1;
        }
    }
    cout << ans;
}