$n \leq 500000$个水管，每秒横坐标加一，纵坐标如果你点击就+1否则-1，问从$(0,0)$飞到$m$处最少点多少次，或者说明无解。

如果能飞到某个水管的高度区间$[L,R]$，那么答案肯定是：高度每相差2，答案相差1，感性理解或自证不难。

所以只需要记能飞到的高度区间以及最低处答案即可。

1 #include
      
        2 #include
       
         3 #include
        
          4 //#include
         
           5 #include
          
            6 //#include
           
             7 //#include
            
              8 //#include
             
               9 using namespace std;10 11 #define LL long long12 int qread()13 {14 char c; int s=0,t=1; while ((c=getchar())<'0' || c>'9') (c=='-') && (t=-1);15 do s=s*10+c-'0'; while ((c=getchar())>='0' && c<='9'); return s*t;16 }17 18 //Pay attention to read!19 20 int n,m;21 #define maxn 50001122 int x[maxn],a[maxn],b[maxn];23 #define LL long long24 int main()25 {26 n=qread(); m=qread();27 for (int i=1;i<=n;i++) {x[i]=qread(); a[i]=qread()+1; b[i]=qread()-1;}28 29 int L=0,R=0; LL ans=0;30 for (int i=1;i<=n;i++)31 {32 int d=x[i]-x[i-1];33 if (L-d>b[i] || R+d
              
               R) {puts("NIE"); return 0;}36 ans+=(d+nl-L)>>1; L=nl;37 }38 printf("%lld\n",ans);39 return 0;40 }