problem

以下の$2$種類のクエリを処理せよ。

  • 時刻$T$に、値段$P$の注文が発生したことが知らされる
  • 時刻$(T-60, T]$で発生する注文の中で最も大きい値段を答える

solution

Use priority queue. $O(N \log N)$.

Sort queries with the time and the type, and add the hypothesis: the type-$1$ queries precedes type-$2$ queries if they has the same time $t$. Then for a type-$1$ query, add the order the priority queue. For a type-$2$ query. See the order whose price is highest in the queue. If the order is expired, then pop and ignore it and see the next one, else answer it.

implementation

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <functional>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
typedef long long ll;
using namespace std;
struct query_t { int type; ll p, t; };
int main() {
    int n; cin >> n;
    vector<query_t> qs(n);
    for (query_t & q : qs) {
        cin >> q.type;
        if (q.type == 1) {
            cin >> q.p >> q.t;
        } else if (q.type == 2) {
            cin >> q.t;
        }
    }
    sort(qs.begin(), qs.end(), [](query_t a, query_t b) {
        return make_pair(a.t, a.type) < make_pair(b.t, b.type);
    });
    auto cmp = [](query_t a, query_t b) {
        return a.p < b.p;
    };
    priority_queue<query_t, priority_queue<query_t>::container_type, decltype(cmp)> que(cmp);
    for (query_t q : qs) {
        if (q.type == 1) {
            que.push(q);
        } else if (q.type == 2) {
            while (not que.empty() and que.top().t <= q.t - 60) que.pop();
            int ans = -1;
            if (not que.empty()) ans = que.top().p;
            cout << ans << endl;
        }
    }
    return 0;
}