Hoj 2245 planktonic triangle cell (Mathematics)

Hello everyone , I meet you again , I'm the king of the whole stack .

Time Limit: 500 MS Memory Limit: 50000 K Total Submit: 129(38 users) Total Accepted: 66(34 users) Rating: Special Judge: No	Time Limit: 500 MS	Memory Limit: 50000 K	Total Submit: 129(38 users)	Total Accepted: 66(34 users)	Rating:	Special Judge: No
Time Limit: 500 MS	Memory Limit: 50000 K
Total Submit: 129(38 users)	Total Accepted: 66(34 users)	Rating:	Special Judge: No
Description
As you can see .Zoidtrip It's a casual game …… Players need to control a speed of 45 degrees downward v Triangle cell that keeps moving , Keep avoiding horizontal obstacles , Each click on the screen can change the direction of travel .[ Can tilt to the left （ Right ）45° Change to oblique right ( Left )45°] Now , Yes n Layer obstacle . The first i Layer obstacles can be seen from the abscissa l[i]~r[i] Through the range of （ contain l[i] And r[i]）, The first i Obstacles on the first floor and i-1 The distance between layer obstacles is d[i]. Excuse me, , Assuming that the direction can be changed infinitely , What level can you advance to at most ? We stipulate that the birth position of players is 0 layer 、 Abscissa for 0 The place of . You can change direction at any real time .
Input
Multiple sets of test data . The first line of each group of test data is two positive integers n and v. Next n That's ok , Each row 3 It's an integer l[i] , r[i] , d[i]. ( N <= 2000000.0 <= All data < 2^31 )
Output
For each set of data . Output one line , Include an integer , Represents the maximum number of layers to advance to .
Sample Input
3 7 1 3 1 4 10 5 8 10 1 4 1 1 1 1 2 5 10 1 1 1 3 5 2
Sample Output
2 4
Hint
“ The first i Obstacles on the first floor and i-1 The distance between layer obstacles is d[i]” therefore d[1] Is the distance between the first floor and the zero floor . Example 1 Explain, for example, the following ： We can move the birth position to the right and down to the first floor, with the coordinates of 1 The place of . Next, you can continue to move all the way down to the right until the coordinate of the second layer is 6 The place of . But you can't move to the third floor anyway 8~10 Between . Example 2 Description such as the following ： (0,0)->(1,1)->(2,2)->(3,1)->(4,3) So get to the fourth floor .
Source
The 5th Harbin University of Technology ACM Programming Competition

PS:

hold Triangle cells are found at the leftmost and rightmost distance that can be reached on each layer and can avoid obstacles !

The code is as follows ：

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define maxn 2000047
LL l[maxn], r[maxn], d[maxn];

int main()
{
    LL n, v;
    while(scanf("%lld%lld",&n,&v)!=EOF)
    {
        LL L = 0,R = 0;
        int ans = 0;
        for(int i=0; i<n; i++)
        {
            scanf("%lld%lld%lld",&l[i],&r[i],&d[i]);
        }
        for(int i = 0; i < n; i++)
        {
            if(l[i] > r[i])
            {
                LL t = r[i];
                r[i] = l[i];
                l[i] = t;
            }
            L-=d[i];
            R+=d[i];
            L = max(l[i],L);
            R = min(r[i],R);
            if(L > R)
            {
                break;
            }
            ans++;
        }
        if(v == 0)
            ans = 0;
        printf("%d\n",ans);
    }
    return 0;
}

Copy

Publisher ： Full stack programmer stack length , Reprint please indicate the source ：https://javaforall.cn/116288.html Link to the original text ：https://javaforall.cn