oj.uz

Submission #965608

# Submission time Handle Problem Language Result Execution time Memory
965608 2024-04-19T02:54:51 Z vjudge1 Trading (IZhO13_trading) C++17
100 / 100
 155 ms 18916 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 69 ms 9076 KB Output is correct
8 Correct 75 ms 8604 KB Output is correct
9 Correct 81 ms 10176 KB Output is correct
10 Correct 95 ms 11516 KB Output is correct
11 Correct 91 ms 10432 KB Output is correct
12 Correct 105 ms 12836 KB Output is correct
13 Correct 108 ms 11736 KB Output is correct
14 Correct 113 ms 12836 KB Output is correct
15 Correct 115 ms 12892 KB Output is correct
16 Correct 123 ms 14996 KB Output is correct
17 Correct 127 ms 13268 KB Output is correct
18 Correct 126 ms 17640 KB Output is correct
19 Correct 128 ms 13248 KB Output is correct
20 Correct 155 ms 18916 KB Output is correct