【BZOJ4723】[POI2017]Flappy Bird

Description

《飞扬的小鸟》是一款风靡的小游戏。在游戏中,小鸟一开始位于(0,0)处,它的目标是飞到横坐标为X的某个位置

上。每一秒,你可以选择点击屏幕,那么小鸟会从(x,y)飞到(x+1,y+1),或者不点击,那么小鸟会飞到(x+1,y-1)

。在游戏中还有n个障碍物,用三元组(x[i],a[i],b[i])描述,表示在直线x=x[i]上,y<=a[i]或者y>=b[i]的部分

都是障碍物,碰到或者擦边都算游戏失败。请求出小鸟从(0,0)飞到目的地最少需要点击多少次屏幕。

Input

第一行包含两个整数n(0<=n<=500000),X(1<=n<=10^9)。

接下来n行,每行三个整数x[i],a[i],b[i](0<x[i]<X,-10^9<=a[i]<b[i]<=10^9)。

数据保证x[i]<x[i+1]。

Output

如果无论如何都飞不到目的地,输出NIE,否则输出点击屏幕的最少次数。

Sample Input

4 11
4 1 4
7 -1 2
8 -1 3
9 0 2

Sample Output

5

HINT

/**************************************************************

    Problem: 4723

    User: ictsing

    Language: C++

    Result: Accepted

    Time:988 ms

    Memory:1288 kb

****************************************************************/

 

//BZOJ4723 [POI2017]Flappy Bird

#include <iostream>

#include <cstdio>

using namespace std;

inline int read()

{

    int num=0,flag=1;

    char ch;

    do{

       ch=getchar();

       if(ch=='-') flag=-1;

    }while(ch<'0'||ch>'9');

    do{

       num=num*10+ch-'0';

       ch=getchar();

    }while(ch>='0'&&ch<='9');

    return num*flag;

}

int main()

{

    int n=read(),m=read();

    int l=0,r=0,lx=0;

    for(int i=1;i<=n;i++)

    {

        int x=read(),d=read(),u=read();

        l=max(d+1,l-x+lx); if((x+l)&1) l++;

        r=min(u-1,r+x-lx); if((x+r)&1) r--;

        if(l>r) {puts("NIE");return 0;}

        lx=x;

    }

    printf("%d\n",(lx+l)/2);

    return 0;

}

 

评论

热度(7)