记录编号	423437	评测结果	AAAAAAAAAA
题目名称	[SOJ 1137] 河床	最终得分	100
用户昵称	kZime	是否通过	通过
代码语言	C++	运行时间	0.033 s
提交时间	2017-07-11 21:03:44	内存使用	4.34 MiB

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

inline char getc() { 
    static char buf[1 << 18], *fs, *ft;
    return (fs == ft 
        && (ft = (fs = buf) + fread(buf, 1, 1 << 18, stdin))
         ,  fs == ft) ? EOF : *fs++;
}

inline int gn() { 
    int k = 0;
    char c = getc();
    for(; !isdigit(c); c = getc());
    for(; isdigit(c); c = getc()) k = k * 10 + c - '0';
    return k;
}

int n, k, x = 1, a[30002], ans, si[30002][16], sa[30002][16];

inline int gt(int l, int r) { //取[l, r]区间极差
    int len = r - l + 1, m = 0;
    while(1 << (m + 1) < len) m++;
    return max(sa[l][m], sa[r - (1 << m) + 1][m])
         - min(si[l][m], si[r - (1 << m) + 1][m]);
}

int main() { 
# ifndef LOCAL
    freopen("riverbed.in", "r", stdin);
    freopen("riverbed.out", "w", stdout);
# endif
    memset(si, 0x7f, sizeof(si));
    n = gn(), k = gn();
    for(int i = 1; i <= n; i++) a[i] = sa[i][0] = si[i][0] = gn();
    for(int i = 1; i <= 15; i++) { 
        for(int j = 1; j <= n - (1 << i) + 1; j++) { 
            sa[j][i] = max(sa[j][i - 1], sa[j + (1 << (i - 1))][i - 1]);
            si[j][i] = min(si[j][i - 1], si[j + (1 << (i - 1))][i - 1]);
        }
    }
    for(int i = 1; i <= n; i++) { 
        if(gt(x, i) <= k) ans = max(ans, i - x + 1);
        else while(gt(x, i) > k) x++;
    }
    printf("%d\n", ans);
}