quhengyi11 的博客

quhengyi11 的博客

题解 P1442 【铁球落地】

posted on 2018-11-01 19:44:05 | under 线段树 |

╮(╯_╰)╭一道码力题。对于我这种蒟蒻超级不友好

直接用线段树作预处理,从下往上扫描线,预处理出每个线段在左边跳和在右边跳能跳到哪一条线段。

接着我们可以打个dp,$dp[i][0/1]$表示起点到达第i个线段左边/右边要多少时间,地面特判一下就行了。

先前疯狂WA,后来自己和std拍出一个数据,才发现自己的flag标记在pushdown的时候没有下放(真的蠢),所以这组数据就放这了。

一个拍出来的数据:

5 3

11 11

1 3 33

2 4 55

4 3 44

7 7 11

9 11 16

输出19

代码:

#include<bits/stdc++.h>
#define fo(i, a, b) for (Re int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (Re int i = (a); i >= (b); --i)
#define edge(i, u) for (Re int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define N 200005
#define Re register
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define lowbit(x) (x & -x)
#define ls (k << 1)
#define rs (k << 1 | 1)
#define mod 1000000007
int n, T, X, Y, a[N], tot, cnt, ans, x, y, w, i, pos, now, dp[N][2], L, R, m, X0, Y0;
struct line{
    int x1, x2, y, l, r;
    friend bool operator < (line qwq, line qaq)
    {
        return qaq.y < qwq.y;
    }
}p[N];
struct tree{
    int v;
    bool flag;
}t[N << 2];
inline void pushdown (int k)
{
    if (t[k].flag)
    {
        t[k].flag = 0;
        t[ls].v = t[rs].v = t[k].v;
        t[rs].flag = t[ls].flag = 1;
    }
}
inline void add (int k, int l, int r)
{
    if (L <= l && R >= r)
    {
        t[k].v = i;
        t[k].flag = 1;
        return;
    }
    pushdown(k);
    int mid = l + r >> 1;
    if (L <= mid) add(ls, l, mid);
    if (mid < R) add(rs, mid + 1, r);
}
inline int query (int k, int l, int r)
{
    if (t[k].flag && l <= now && now <= r || l == r && l == now)
    {
        return t[k].v;
    }
    pushdown(k);
    int mid = l + r >> 1;
    if (now <= mid) return query(ls, l, mid);
    if (mid < now) return query(rs, mid + 1, r);
}
inline int abs (int x) {return x < 0 ? -x : x;}
inline int dis (int x1, int y1, int x2, int y2) {return abs(x1 - x2) + abs(y1 - y2);}
int main ()
{
    scanf("%d %d", &n, &m);
    scanf("%d %d", &X0, &Y0);
    fo (i, 1, n)
    {
        scanf("%d %d %d", &p[i].y, &p[i].x1, &p[i].x2);
        a[i] = p[i].x1;
        a[i + n] = p[i].x2;
    }
    std::sort(a + 1, a + n + n + 1);
    cnt = std::unique(a + 1, a + n + n + 1) - a - 1;
    std::sort(p + 1, p + n + 1);//y值从高到低
    fo (i, 1, n)
        if (p[i].y <= Y0 && p[i].x1 <= X0 && p[i].x2 >= X0)
        {
            pos = i;
            break;
        }
    int j;
    i = 0;
    L = 1; R = cnt;
    add(1, 1, cnt);
    for (i = n; i; --i)
    {
        now = std::lower_bound(a + 1, a + cnt + 1, p[i].x1) - a;
        j = query(1, 1, cnt);
        if (p[i].y - p[j].y <= m) p[i].l = j; else p[i].l = -1;
        now = std::lower_bound(a + 1, a + cnt + 1, p[i].x2) - a;
        j = query(1, 1, cnt);
        if (p[i].y - p[j].y <= m) p[i].r = j; else p[i].r = -1;
        L = std::lower_bound(a + 1, a + cnt + 1, p[i].x1) - a;
        R = std::lower_bound(a + 1, a + cnt + 1, p[i].x2) - a;
        add(1, 1, cnt);
    }
    memset(dp, 0x3f, sizeof dp);
//    fo (i, 1, n)
//        printf("i = %d l = %d r = %d\n", i, p[i].l, p[i].r);
    dp[pos][0] = dis(X0, Y0, p[pos].x1, p[pos].y);
    dp[pos][1] = dis(X0, Y0, p[pos].x2, p[pos].y);
    fo (i, 1, n)
    {
        int nxt = p[i].l;
        if (nxt != -1)
        {
            if (!nxt)
                dp[0][0] = std::min(dp[0][0], dp[i][0] + p[i].y);
            else
            {
                dp[nxt][0] = std::min(dp[nxt][0], dp[i][0] + dis(p[i].x1, p[i].y, p[nxt].x1, p[nxt].y));
                dp[nxt][1] = std::min(dp[nxt][1], dp[i][0] + dis(p[i].x1, p[i].y, p[nxt].x2, p[nxt].y));
            }
        }
        nxt = p[i].r;
        if (nxt != -1)
        {
            if (!nxt)
                dp[0][0] = std::min(dp[0][0], dp[i][1] + p[i].y);
            else
            {
                dp[nxt][0] = std::min(dp[nxt][0], dp[i][1] + dis(p[i].x2, p[i].y, p[nxt].x1, p[nxt].y));
                dp[nxt][1] = std::min(dp[nxt][1], dp[i][1] + dis(p[i].x2, p[i].y, p[nxt].x2, p[nxt].y));
            }
        }
    }
    printf("%d\n", dp[0][0]);
    return 0;
}