自动搬运

查看原文

来自洛谷，原作者为

	Elma_ blog：https://www.cnblogs.com/came11ia

搬运于2025-08-24 22:25:32，当前版本为作者最后更新于2022-09-28 19:21:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

判断无解是容易的，不妨只考虑有解的情况。以时间为横轴、车数为纵轴画出一条折线，可以发现所有人的等待时间之和恰好是折线在横轴下方的部分和横轴围成的图形的面积。

考虑如何处理多次询问：先算出 $b_i =0$ 时的答案，此时折线在横轴下方的部分和横轴所围成的图形可以拆分成若干高度不同的矩形。当 $b_i > 0$ 时我们需要维护这些矩形向上平移 $b_i$ 后的答案，将矩形按高度排序，询问按 $b_i$ 排序后用指针维护一下即可。视 $n,q$ 同阶，则时间复杂度为 $O(n \log n)$。

/*
最黯淡的一个　梦最为炽热
万千孤单焰火　让这虚构灵魂鲜活
至少在这一刻　热爱不问为何
存在为将心声响彻
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N = 2e5 + 5;

struct node {
    int x, id;
    bool operator < (const node &b) const {
        return x < b.x;
    }
} p[N];
int n, m, q, a[N], s[N], t[N]; 
int vr[N], bak; 
LL s1, s2, ans[N];

signed main(void) {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        char ch;
        cin >> ch >> t[i] >> a[i];
        a[i] *= (ch == '+' ? 1 : -1);
    }
    for (int i = 1; i <= n; i++) {
        s[i] = s[i - 1] + a[i];
        if (i < n) t[i] = t[i + 1] - t[i];
    }
    for (int i = 1; i <= n; i++) if (s[i] < 0) {
        vr[++bak] = i;
        s1 += 1ll * t[i] * (-s[i]);
        s2 += t[i];
    }  
    sort(vr + 1, vr + bak + 1, [&](const int &i, const int &j) {
        return s[i] > s[j];
    });
    for (int i = 1; i <= q; i++) cin >> p[i].x, p[i].id = i;
    sort(p + 1, p + q + 1);
    int j = 1;
    for (int i = 1; i <= q; i++) {
        while (j <= bak && -s[vr[j]] <= p[i].x) {
            s1 -= 1ll * t[vr[j]] * -s[vr[j]];
            s2 -= t[vr[j]];
            j++;
        }
        ans[p[i].id] = (s[n] + p[i].x < 0 ? -1 : s1 - 1ll * p[i].x * s2); 
    }
    for (int i = 1; i <= q; i++)
        ans[i] == -1 ? puts("INFINITY") : printf("%lld\n", ans[i]);
    return 0;   
}