题解：P11833 [省选联考 2025] 推箱子

2huk · 2025-03-02 18:02:01 · 题解

有一个显然但是我想不到的贪心：将所有箱子按照 t 即截止时间从小到大排序，然后依次处理每个箱子，将这个箱子从 a_i 移动到 b_i。如果路上有箱子挡路就推着一起走。

发现这个东西就是 窄巷中的高桥君。复制过来即可。

// Problem: F - Takahashi in Narrow Road
// Contest: AtCoder - AtCoder Beginner Contest 371
// URL: https://atcoder.jp/contests/abc371/tasks/abc371_f
// Memory Limit: 1024 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define int ll

const int N = 1e6 + 10, INF = 1e14;

int n, a[N];

struct Node {
    int l, r, v, tag;
}tr[N << 2];

int sum(int x, int y) {
    return (x + x + y - 1) * y / 2;
}

void pushup(int u) {
    tr[u].v = tr[u << 1].v + tr[u << 1 | 1].v;
}

void calc(int u, int d) {
    tr[u].tag = d;
    tr[u].v = sum(d, tr[u].r - tr[u].l + 1);
}

void pushdown(int u) {
    if (tr[u].tag != -INF) {
        calc(u << 1, tr[u].tag);
        calc(u << 1 | 1, tr[u].tag + tr[u << 1].r - tr[u << 1].l + 1);
        tr[u].tag = -INF;
    }
}

void build(int u, int l, int r) {
    tr[u].l = l, tr[u].r = r, tr[u].v = a[l], tr[u].tag = -INF;
    if (l != r) {
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int l, int r, int d) {
    if (tr[u].l >= l && tr[u].r <= r) calc(u, d + tr[u].l - l);
    else {
        int mid = tr[u].l + tr[u].r >> 1;
        pushdown(u);
        if (l <= mid) modify(u << 1, l, r, d);
        if (r > mid) modify(u << 1 | 1, l, r, d);
        pushup(u);
    }
}

int query(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].v;
    int mid = tr[u].l + tr[u].r >> 1, res = 0;
    pushdown(u);
    if (l <= mid) res = query(u << 1, l, r);
    if (r > mid) res += query(u << 1 | 1, l, r);
    return res;
}

struct Box {
    int a, b, c;
}box[N];

int p[N];

bool solve() {
    cin >> n;

    for (int i = 1; i <= n; ++ i ) {
        cin >> box[i].a >> box[i].b >> box[i].c;
    }

    iota(p + 1, p + n + 1, 1);

    sort(p + 1, p + n + 1,
        [&](int x, int y) {
            return box[x].c < box[y].c;
        });

    for (int i = 1; i <= n; ++ i ) a[i] = box[[p[i]]].a;
    build(1, 1, n);

    int q, ans = 0;

    for (int i = 1; i <= n; ++ i ) {
        int t = p[i], g = box[p[i]].b;

        if (query(1, t, t) == g) continue;
        if (query(1, t, t) < g) {
            int lo = t, hi = n, res = -1;

            while (lo <= hi) {
                int mid = lo + hi >> 1;
                if (query(1, mid, mid) - g + 1 < mid - t + 1) {
                    res = mid;
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
            // cout << res << '\n';

            ans += sum(g, res - t + 1) - query(1, t, res);
            // cout << g << ' ' << res - t + 1 << ' ' << query(1, t, res) << '\n';
            modify(1, t, res, g);
        } else {
            int lo = 1, hi = t, res = -1;

            while (lo <= hi) {
                int mid = lo + hi >> 1;
                if (g - query(1, mid, mid) + 1 < t - mid + 1) {
                    res = mid;
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }
            }
            // cout << res << '\n';

            ans += query(1, res, t) - sum(g - (t - res + 1) + 1, t - res + 1);
            // cout << g - (t - res + 1) + 1 << ' ' << t - res + 1 << ' ' << query(1, res, t) << '\n';
            modify(1, res, t, g - (t - res + 1) + 1);
        }

    // cout << i << ' ' << box[i].a << ' ' << box[i].b << ' ' << box[i].c << '\n';
        if (ans > box[p[i]].c) return false;
    }

    return true;
}

signed main() {
    int c, T;
    cin >> c >> T;
    while (T -- ) cout << (solve() ? "Yes\n" : "No\n");
    return 0;
}