求调 WA+RE 10
查看原帖
求调 WA+RE 10
750803
_Revenge_楼主2023/2/19 10:23
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;

const int N = 1e5 + 50;
const int M = 1e5 + 50;
const int Mod = 1e9 + 7;

#define int long long

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

struct node
{
    int id, fir, len, vol;
} a[N];

int n;

bool cmp(node x, node y)
{
    if (x.fir != y.fir)
        return x.fir < y.fir;
    else
        return x.vol > y.vol;
}

struct que
{
    int id, fir, len, vol;
    bool operator<(const que &o) const
    {
        if (o.vol != vol)
            return o.vol > vol;
        else
            return o.fir < fir;
    }
};

priority_queue<que> q;

signed main()
{
    while (scanf("%lld", &a[n + 1].id) != EOF)
    {
        ++n;
        scanf("%lld%lld%lld", &a[n].fir, &a[n].len, &a[n].vol);
    }
    sort(a + 1, a + n + 1, cmp);
    int now = 0, res = 1;
    while (res <= n || !q.empty())
    {
        if (q.empty() && res <= n)
            q.push((que){a[res].id, a[res].fir, a[res].len, a[res].vol}), ++res;
        while (res <= n && now >= a[res].fir)
            q.push((que){a[res].id, a[res].fir, a[res].len, a[res].vol}), ++res;
        que tmp = q.top();
        q.pop();
        if (res > n || tmp.vol >= a[res].vol || tmp.len + max(tmp.fir, now) < a[res].fir)
        {
            now = max(now, tmp.fir) + tmp.len;
            printf("%d %d\n", tmp.id, now);
        }
        else
        {
            now = max(now, tmp.fir);
            tmp.len -= (a[res].fir - now);
            now = a[res].fir;
            q.push((que){tmp.id, tmp.fir, tmp.len, tmp.vol});
        }
    }
    return 0;
}
2023/2/19 10:23
加载中...