记录编号	605657	评测结果	WAWWA
题目名称	284.[NOI 1999]内存分配	最终得分	40
用户昵称	ChenBp	是否通过	未通过
代码语言	C++	运行时间	0.085 s
提交时间	2025-09-05 22:03:45	内存使用	3.30 MiB

#include <iostream>
#include <queue>
using namespace std;
struct listnode {
    int ms, md;
    listnode *next, *from;
};
listnode *head = NULL;
struct wai {
    int m, p, t;
};
queue<wai> waiting;
struct usep {
    int ms, md, t;
    bool operator<(const usep &y) const { return t > y.t; }
};
priority_queue<usep> use;
void add(int ms, int md, listnode *from, listnode *next) {
    listnode *now = new listnode;
    now->ms = ms;
    now->md = md;
    now->from = from;
    now->next = next;
    if (from)
        from->next = now;
    if (next)
        next->from = now;
    if (from && from->md + 1 == now->ms) {
        from->md = now->md;
        from->next = now->next;
        if (now->next)
            now->next->from = from;
        delete now;
        now = from;
    }
    if (next && now->md + 1 == next->ms) {
        now->md = next->md;
        now->next = next->next;
        if (next->next)
            next->next->from = now;
        delete next;
    }
    if (!now->from)
        head = now;
}
void addl(int ms, int md) {
    if (!head) {
        head = new listnode{ms, md, NULL, NULL};
        return;
    }
    listnode *pos = head, *prev = NULL;
    while (pos && pos->ms < ms) {
        prev = pos;
        pos = pos->next;
    }
    add(ms, md, prev, pos);
}
pair<int, int> findmem(int m) {
    for (auto i = head; i != NULL; i = i->next) {
        int len = i->md - i->ms + 1;
        if (len >= m) {
            int L = i->ms;
            int R = L + m - 1;
            if (R == i->md) {
                if (i->from)
                    i->from->next = i->next;
                if (i->next)
                    i->next->from = i->from;
                if (i == head)
                    head = i->next;
                delete i;
            } else {
                i->ms = R + 1;
            }
            return {L, R};
        }
    }
    return {-1, -1};
}
int main() {
    int n, t, m, p;
    cin >> n;
    head = new listnode{0, n - 1, NULL, NULL};
    int last = 0, wit = 0;
    while (1) {
        cin >> t >> m >> p;
        if (t == 0 && m == 0 && p == 0)
            break;
        last = t;
        while (!use.empty() && use.top().t <= t) {
            auto top = use.top();
            use.pop();
            addl(top.ms, top.md);
        }
        while (!waiting.empty()) {
            auto now = waiting.front();
            auto place = findmem(now.m);
            if (place.first != -1) {
                int start_time = max(t, now.t);
                use.push({place.first, place.second, start_time + now.p});
                waiting.pop();
            } else
                break;
        }
        auto place = findmem(m);
        if (place.first != -1) {
            use.push({place.first, place.second, t + p});
        } else {
            waiting.push({m, p, t});
            ++wit;
        }
    }
    while (!waiting.empty() || !use.empty()) {
        if (use.empty()) {
            bool scheduled = false;
            while (!waiting.empty()) {
                auto now = waiting.front();
                auto place = findmem(now.m);
                if (place.first != -1) {
                    int start_time = max(last, now.t);
                    use.push({place.first, place.second, start_time + now.p});
                    waiting.pop();
                    scheduled = true;
                } else
                    break;
            }
            if (!scheduled)
                break;
        } else {
            last = use.top().t;
            while (!use.empty() && use.top().t <= last) {
                auto top = use.top();
                use.pop();
                addl(top.ms, top.md);
            }
            while (!waiting.empty()) {
                auto now = waiting.front();
                auto place = findmem(now.m);
                if (place.first != -1) {
                    int start_time = max(last, now.t);
                    use.push({place.first, place.second, start_time + now.p});
                    waiting.pop();
                } else
                    break;
            }
        }
    }
    cout << last << endl << wit;
}