#include<cstdio>  
#include<algorithm>  
#include<cstring>  
using namespace std;  
const int L=1000005,inf=0x3f3f3f3f;  
bool ck[L];  
struct Line  
{  
    int left,right,val;  
}line[L*4];  
void build(int now,int left,int right)  
{  
    line[now].left=left;  
    line[now].right=right;  
    line[now].val=inf;  
    if(left==right)return;  
    build(now*2,left,(left+right)>>1);  
    build(now*2+1,(left+right)/2+1,right);  
}  
void updata(int now,int pos,int val)  
{  
    int ll=line[now].left,rr=line[now].right,mid;  
    if(ll==pos&&rr==pos)  
    {  
        line[now].val=min(line[now].val,val);  
        return;  
    }  
    mid=(ll+rr)>>1;  
    if(pos<=mid)  
        updata(now*2,pos,val);  
    else  
        updata(now*2+1,pos,val);  
    line[now].val=min(line[now*2].val,line[now*2+1].val);  
}  
int getmin(int now,int left,int right)  
{  
    int ll=line[now].left,rr=line[now].right,mid;  
    if(ll==left&&rr==right)  
        return line[now].val;  
    mid=(ll+rr)>>1;  
    if(right<=mid)  
        return getmin(now*2,left,right);  
    else if(left>mid)  
        return getmin(now*2+1,left,right);  
    else  
        return min(getmin(now*2,left,mid),getmin(now*2+1,mid+1,right));  
}  
int main()  
{  
    int n,len,a,b,ans;  
    while(scanf("%d%d",&n,&len)!=EOF)  
    {  
        build(1,0,len/2);  
        scanf("%d%d",&a,&b);  
        memset(ck,true,sizeof(ck));  
        for(int i=0,x,y;i<n;i++)  
        {  
            scanf("%d%d",&x,&y);  
            memset(ck+x+1,false,(y-x-1)*sizeof(bool));  
        }  
        updata(1,0,0);  
        for(int i=a*2;i<=len;i+=2)  
        {  
            if(ck[i])  
            {  
                int x=i/2-b,y=i/2-a,tp;  
                x=max(0,x);  
                tp=getmin(1,x,y);  
                if(tp==inf)  
                    tp--;  
                updata(1,i/2,tp+1);  
            }  
        }  
        ans=getmin(1,len/2,len/2);  
        printf("%d\n",ans<inf?ans:-1);  
    }  
    return 0;  
}  

• Re:此题绝壁有问题~下面的ac程序对于数据 1 11 1 2 3 6竟然输出3~其实应该是-1 (2254) 1500012857 2016-06-22 10:03:41
  • Re:此题绝壁有问题~下面的ac程序对于数据 1 11 1 2 3 6竟然输出3~其实应该是-1 (17) 1500012857 2016-06-22 10:04:08