1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

#include <cstdio>
#include <algorithm>
using namespace std;
int tot, a[150005], b[150005], n, m, h, ans;
inline int getint() {
    register int r = 0; register bool b = true; register char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') b = false; c = getchar(); }
    while (c >= '0' && c <= '9') { r = (r<<1)+(r<<3) + c - '0'; c = getchar(); }
    return b ? r : -r;
}
struct Node {
    int val, tag;
    Node *lc, *rc;
    void add(int x) {
        val += x;
        tag += x;
    }
} tr[300005], *rt;
Node *build(int l, int r) {
    Node *ret = tr + (tot++);
    if (l == r) {
        ret->val = l - m - 1;
    }
    else {
        int mid = (l + r) >> 1;
        ret->lc = build(l, mid);
        ret->rc = build(mid + 1, r);
        ret->val = min(ret->lc->val, ret->rc->val);
    }
    return ret;
}
void change(Node *x, int l, int r, int ll, int rr, int val) {
    if (ll <= l && r <= rr) x->add(val);
    else {
        x->lc->add(x->tag);
        x->rc->add(x->tag);
        x->tag = 0;
        int mid = (l + r) >> 1;
        if (ll <= mid) change(x->lc, l, mid, ll, rr, val);
        if (rr > mid) change(x->rc, mid + 1, r, ll, rr, val);
        x->val = min(x->lc->val, x->rc->val);
    }
}
int main() {
    n = getint(); m = getint(); h = getint();
    for (int i = 1; i <= m; ++i) b[i] = h - getint();
    sort(b + 1, b + m + 1);
    for (int i = 1; i <= n; ++i) a[i] = upper_bound(b + 1, b + m + 1, getint()) - b - 1;
    rt = build(1, m);
    for (int i = 1; i < m; ++i)
        if (a[i] > 0) change(rt, 1, m, 1, a[i], 1);
    for (int i = 1, j = m; j <= n; ++i, ++j) {
        if (a[j] > 0) change(rt, 1, m, 1, a[j], 1);
        if (rt->val >= 0) ++ans;
        if (a[i] > 0) change(rt, 1, m, 1, a[i], -1);
    }
    printf("%d\n", ans);
}