Submission #968551

#	Time	Username	Problem	Language	Result	Execution time	Memory
968551		njoop	Trading (IZhO13_trading)	C++14	100 / 100	146 ms	17692 KiB

trading

#include <bits/stdc++.h>

using namespace std;

struct trader {
    int l, r, val;
};

struct cmp1 {
    bool operator()(const trader &a, const trader &b) {
        return a.r < b.r;
    }
};

struct cmp2 {
    bool operator()(const trader &a, const trader &b) {
        return a.val < b.val;
    }
};

int n, m, il, ir, ival, ans[300010];
priority_queue<trader, vector<trader>, cmp1> store;
priority_queue<trader, vector<trader>, cmp2> pq;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    for(int i=0; i<m; i++) {
        cin >> il >> ir >> ival;
        store.push({il, ir, ival+n-il});
    }
    for(int i=n; i>0; i--) {
        while(store.size() && i <= store.top().r) {
            pq.push(store.top());
            store.pop();
        }
        while(pq.size() && pq.top().l > i) pq.pop();
        if(pq.empty()) continue;
        ans[i] = pq.top().val - (n-i);
    }
    for(int i=1; i<=n; i++) {
        cout << ans[i] << " ";
    } 
    return 0;
}

• Subtask 1: 100 / 100