A1568 复杂均衡

// A1568 复杂均衡 —— 每台计算机一个「按结束时间排序」的小根堆
//
// 任务 (a, b, c, d)：时刻 a 把任务分给 b 号计算机，耗时 c 秒、占用算力 d。
// 时刻 a 到来时，先把 b 号计算机上**已经结束**的任务占用的算力还回来，
// 再看剩余算力：够就分配（扣掉 d，并记录该任务占用到 a+c 时刻），不够就输出 -1。
// 任务按 a 严格递增给出，所以每个计算机只需要一个小根堆存「正在运行的任务」。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<ll> rest(n + 1);
    for (int i = 1; i <= n; i++) cin >> rest[i]; // 初始剩余算力就是运算能力

    // 每台计算机上正在运行的任务：(结束时刻, 占用的算力)，按结束时刻的小根堆
    vector<priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>>> heap(n + 1);

    for (int i = 0; i < m; i++) {
        ll a, c, d;
        int b;
        cin >> a >> b >> c >> d;

        auto &q = heap[b];
        // 1) 归还已经结束的任务所占的算力
        while (!q.empty() && q.top().first <= a) {
            rest[b] += q.top().second;
            q.pop();
        }
        // 2) 剩余算力不足就取消这次分配
        if (rest[b] < d) {
            cout << -1 << '\n';
            continue;
        }
        // 3) 分配成功：扣掉算力，并登记这个任务直到 a+c 时刻
        rest[b] -= d;
        q.push({a + c, d});
        cout << rest[b] << '\n';
    }
    return 0;
}