【数据结构】事件模拟

https://codeforces.com/contest/1239/problem/C

人为规定事件的优先级

永续事件用个触发器触发

int n;
ll p;
ll ans[100005];

struct Event {
    ll Time;
    int Type, Id;
    bool operator<(const Event &event)const {
        if (Time != event.Time)
            return Time > event.Time;
        if (Type != event.Type)
            return Type > event.Type;
        return Id > event.Id;
    }
};

set<int> Queue;
set<int> Want;
priority_queue<Event>PQ;

void solve() {
    scanf("%d%lld", &n, &p);
    for (int i = 1; i <= n; ++i) {
        ll ti;
        scanf("%lld", &ti);
        PQ.push({ti, 1, i});
    }
    ll curTime = 0;
    ll QueueTime = 0;
    while (!PQ.empty()) {
        // 时间流逝
        if (curTime < PQ.top().Time) {
            curTime = PQ.top().Time;
            QueueTime = max(QueueTime, curTime);
            continue;
        }
        Event e = PQ.top();
//        printf("  time=%lld type=%d id=%d ", e.Time, e.Type, e.Id);
        PQ.pop();
        if (e.Type == 0) {
            // 出队
            Queue.erase(e.Id);
            if (Queue.empty())
                QueueTime = curTime;
            ans[e.Id] = e.Time;
        } else 
            // 进入want
            Want.insert(e.Id);
        // 下一事件已经到达
        if (!PQ.empty() && curTime >= PQ.top().Time)
            continue;
        // 下一事件尚未到达，处理永续事件
        if (Want.size() && (Queue.empty() || *Want.begin() < *Queue.begin())) {
            e.Id = *Want.begin();
            Want.erase(e.Id);
            Queue.insert(e.Id);
            e.Type = 0;
            QueueTime = max(QueueTime, curTime);
            QueueTime += p;
            e.Time = QueueTime;
            PQ.push(e);
       }
    }
    for (int i = 1; i <= n; ++i)
        printf("%lld%c", ans[i], " 
"[i == n]);
}