Submission

Score: 30

User: tHeNyXs

Problemset: Red Zone

Language: cpp

Time: 1.090 second

Submitted On: 2026-03-05 18:39:50

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

struct tree {
    vector<int> lazy, value;
    
    tree(int n) {
        lazy.resize(4*n, 0);
        value.resize(4*n);
    }

    void create(int idx, int l, int r, vector<int> a) {
        if (l == r) {
            value[idx] = a[l];
            return;
        }

        int mid = (l+r)/2;
        create(idx*2, l, mid, a);
        create(idx*2+1, mid+1, r, a);
        value[idx] = max(value[idx*2], value[idx*2+1]);
    }

    void updateValue(int idx) {
        value[idx*2] += lazy[idx];
        lazy[idx*2] += lazy[idx];

        value[idx*2+1] += lazy[idx];
        lazy[idx*2+1] += lazy[idx];

        lazy[idx] = 0;
    }

    void update(int idx, int l, int r, int tl, int tr, int d) {
        if (tr < l || tl > r) return;

        if (tl <= l && r <= tr) {
            value[idx] += d;
            lazy[idx] += d;
            // cout << "L : " << tl << " | R : " << tr << '\n';
            return;
        }

        if (lazy[idx] != 0) updateValue(idx);

        int mid = (l+r)/2;
        update(idx*2, l, mid, tl, tr, d);
        update(idx*2+1, mid+1, r, tl, tr, d);

        value[idx] = max(value[idx*2], value[idx*2+1]);
    }

};

int main() {
    ios_base::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];

    tree t(n);
    t.create(1, 1, n, a);
    int ans = -1;
    for (int i = 1; i <= m; ++i) {
        int pos; cin >> pos;
        int L = max(1, pos-l);
        int R = min(n, pos+l);

        // for (int j = 1; j < 4*n; ++j) {
        //     cout << t.value[j] << " ";
        // }
        // cout << '\n';
        t.update(1, 1, n, L, R, -d);

        if (t.value[1] <= 0 && ans == -1) ans = i;
        
        // cout << "I : " << i << "\n";
        // for (int j = 1; j < 4*n; ++j) {
        //     cout << t.value[j] << " ";
        // }
        // cout << "\n\n";
    }
    cout << ans;

    return 0;
}