oj.uz

Submission #681952

# Submission time Handle Problem Language Result Execution time Memory
681952 2023-01-14T23:36:54 Z speedyArda Trading (IZhO13_trading) C++14
100 / 100
 490 ms 44696 KB 
#include "bits/stdc++.h"
using namespace std;

using ll = long long;
const int MAXN = 300005;
vector<vector<pair<ll, pair<ll, ll>>>> beginr(MAXN), endr(MAXN);

int main()
{
    ll n, m;
    cin >> n >> m;
    multiset<pair<ll, pair<ll, ll>>> curr;
    for (int i = 1; i <= m; i++)
    {
        pair<ll, pair<ll, ll>> temp;
        ll f, s, t;
        cin >> f >> s >> t;
        temp.first = t;
        temp.second.first = f;
        temp.second.second = s;
        beginr[f].push_back(temp);
        endr[s + 1].push_back(temp);
    }
    for (int day = 1; day <= n; day++)
    {
        for (pair<ll, pair<ll, ll>> e : endr[day])
        {
            curr.erase(curr.find({e.first - e.second.first, {e.second.first, e.second.second}}));
        }

        for (pair<ll, pair<ll, ll>> e : beginr[day])
        {
            curr.insert({e.first - e.second.first, {e.second.first, e.second.second}});
        }
        pair<ll, pair<ll, ll>> maxi;
        if (curr.size() > 0)
        {

            auto it = curr.end();
            it--;
            maxi = *(it);
            cout << (maxi.first + maxi.second.first) + day - maxi.second.first;
        }
        else
        {
            cout << "0";
        }
        // if (day == 5)
        // cout << maxi.first << " " << maxi.second << "\n";

        if (day != n)
            cout << " ";
    }
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14292 KB Output is correct
2 Correct 8 ms 14292 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 9 ms 14420 KB Output is correct
5 Correct 9 ms 14544 KB Output is correct
6 Correct 11 ms 14676 KB Output is correct
7 Correct 224 ms 30132 KB Output is correct
8 Correct 255 ms 31104 KB Output is correct
9 Correct 261 ms 33224 KB Output is correct
10 Correct 300 ms 36700 KB Output is correct
11 Correct 281 ms 33068 KB Output is correct
12 Correct 335 ms 39396 KB Output is correct
13 Correct 329 ms 36000 KB Output is correct
14 Correct 368 ms 38436 KB Output is correct
15 Correct 418 ms 40728 KB Output is correct
16 Correct 410 ms 39992 KB Output is correct
17 Correct 392 ms 40276 KB Output is correct
18 Correct 433 ms 44584 KB Output is correct
19 Correct 401 ms 41152 KB Output is correct
20 Correct 490 ms 44696 KB Output is correct