Codeforces Round #278 (Div. 1), problem: (B) Strip

遞增區間，雖然比賽時寫二分搜

有點G
設錯INF
Pretest 過
System 沒過

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<cmath>
#define INF 1000000001
using namespace std;
typedef long long int int64;
int tmin[600000];
int tmax[600000];
int arr[100000];
int base;
void init(int n){
    base = (1<<(int)(ceil(log2(n+4)))) - 1;
    for(int lx = 1;lx <= 2*base+1;lx++)
        tmin[lx] = INF, tmax[lx] = -INF;

    for(int lx = 0;lx < n;lx++)
        tmin[base+lx+2] = arr[lx],
        tmax[base+lx+2] = arr[lx];

    for(int lx = base;lx;lx--){
        tmin[lx] = min(tmin[lx+lx], tmin[lx+lx+1]);
        tmax[lx] = max(tmax[lx+lx], tmax[lx+lx+1]);
    }
    return;
}
int qdet(int a, int b){
    a+=2, b+=2;
    int gmin = INF, gmax = -INF;
    for(a += base-1, b += base+1;a^b^1;a>>=1, b>>=1){
        if(~a&1) gmin = min(gmin, tmin[a^1]), gmax = max(gmax, tmax[a^1]);
        if(b&1) gmin = min(gmin, tmin[b^1]), gmax = max(gmax, tmax[b^1]);
    }
    return gmax-gmin;
}
int dp[100003];
int cut[100003]; int ccut = 0;
int main()
{
    int n, s, l;
    scanf("%d %d %d", &n, &s, &l);
    for(int lx = 0;lx < n;lx++)
        scanf("%d", arr+lx);
    init(n);
    int ptr = 0;
    cut[0] = -1;ccut++;
    for(int lx = 0;lx < n;lx++){
        //printf("%d\n", lx);
        for(;ptr < ccut;ptr++)
            if(qdet(cut[ptr]+1, lx) <= s)
                break;
        if(lx-cut[ptr]>= l and qdet(cut[ptr]+1, lx) <= s){
            //printf("find cut %d at %d\n", cut[right], right);
            if(cut[ptr] == -1)
                dp[lx] = 1;
            else
                dp[lx] = 1+dp[cut[ptr]];
            cut[ccut++] = lx;
        }else
            dp[lx] = -1;
        //printf("dp%d = %d\n", lx , dp[lx]);
    }
    printf("%d\n", dp[n-1]);
    return 0;
}