338E - Optimize - CodeForces Solution

#include <bits/stdc++.h>
#define ls p << 1
#define rs ls | 1
#define mid ((l + r) >> 1)
using namespace std;
constexpr int N = 150005, M = N * 8;
int n, m, h, a[N], b[N], o;
vector<int> A;
int get(int x) {
    return upper_bound(A.begin(), A.end(), x) - A.begin();
}
int mn[M], add[M];
void pull(int p) {
    mn[p] = min(mn[ls], mn[rs]);
}
void apply(int p, int t) {
    mn[p] += t;
    add[p] += t;
}
void push(int p) {
    if (add[p]) {
        apply(ls, add[p]);
        apply(rs, add[p]);
        add[p] = 0;
    }
}
void change(int x, int y, int z, int p = 1, int l = 1, int r = o) {
    if (x <= l && r <= y) {
        return apply(p, z);
    }
    push(p);
    if (x <= mid) {
        change(x, y, z, ls, l, mid);
    }
    if (mid < y) {
        change(x, y, z, rs, mid + 1, r);
    }
    pull(p);
}
int main() {
    cin >> n >> m >> h;
    for (int i = 1; i <= m; i++) {
        cin >> b[i];
        b[i] = h - b[i];
        A.push_back(b[i]);
    }
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        A.push_back(a[i]);
    }
    sort(A.begin(), A.end());
    A.erase(unique(A.begin(), A.end()), A.end());
    o = A.size();
    for (int i = 1; i <= m; i++) {
        change(get(b[i]), o, 1);
        change(get(a[i]), o, -1);
    }
    int cnt = 0;
    for (int i = 1; i <= n - m + 1; i++) {
        cnt += mn[1] >= 0;
        change(get(a[i]), o, 1);
        if (i + m <= n) {
            change(get(a[i + m]), o, -1);
        }
    }
    cout << cnt << "\n";
    return 0;
}