oj.uz

Submission #90570

# Submission time Handle Problem Language Result Execution time Memory
90570 2018-12-22T12:38:22 Z popovicirobert Trading (IZhO13_trading) C++14
100 / 100
 474 ms 34580 KB 
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define ld long double
// 217
// 44

using namespace std;

const int MAXN = (int) 3e5;

int x[MAXN + 1], l[MAXN + 1], r[MAXN + 1];

struct Data {
    int pos;
    bool operator <(const Data &other) const {
        if(x[pos] - l[pos] == x[other.pos] - l[other.pos]) {
            return pos < other.pos;
        }
        return x[pos] - l[pos] > x[other.pos] - l[other.pos];
    }
};

multiset <Data> mst;

vector <int> upd[MAXN + 1];

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, n, m;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for(i = 1; i <= m; i++) {
        cin >> l[i] >> r[i] >> x[i];
        upd[l[i]].push_back(i);
        upd[r[i] + 1].push_back(-i);
    }
    for(i = 1; i <= n; i++) {
        for(auto it : upd[i]) {
            if(it < 0) {
                mst.erase(mst.find({-it}));
            }
            else {
                mst.insert({it});
            }
        }
        if(mst.size() == 0) {
            cout << 0 << " ";
        }
        else {
            auto it = *mst.begin();
            cout << x[it.pos] - l[it.pos] + i << " ";
        }
    }
    //cin.close();
    //cout.close();
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 8 ms 7544 KB Output is correct
3 Correct 8 ms 7544 KB Output is correct
4 Correct 9 ms 7632 KB Output is correct
5 Correct 9 ms 7660 KB Output is correct
6 Correct 11 ms 7844 KB Output is correct
7 Correct 219 ms 19140 KB Output is correct
8 Correct 257 ms 23956 KB Output is correct
9 Correct 263 ms 27556 KB Output is correct
10 Correct 281 ms 28024 KB Output is correct
11 Correct 234 ms 28668 KB Output is correct
12 Correct 316 ms 30508 KB Output is correct
13 Correct 316 ms 30508 KB Output is correct
14 Correct 314 ms 30508 KB Output is correct
15 Correct 362 ms 31228 KB Output is correct
16 Correct 385 ms 31228 KB Output is correct
17 Correct 397 ms 31228 KB Output is correct
18 Correct 466 ms 34580 KB Output is correct
19 Correct 422 ms 34580 KB Output is correct
20 Correct 474 ms 34580 KB Output is correct