제출 #681941

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
681941		speedyArda	거래 (IZhO13_trading)	C++14	0 / 100	8 ms	14408 KiB

trading

#include "bits/stdc++.h"
using namespace std;

using ll = long long;
const int MAXN = 300005;
vector<vector<pair<ll, ll>>> beginr(MAXN), endr(MAXN);
/*pair<ll, ll> seg[4 * MAXN];
void push(int v)
{
    seg[v * 2] = seg[v * 2 + 1] = seg[v];
    lazy[v * 2] = lazy[v * 2 + 1] = lazy[v];
}
void update(int v, int tl, int tr, int l, int r, pair<ll, ll> change )
{
    if(l > tr || r < tl)
        return;
    if(l == tl && r == tr)
    {
        if(seg[v] < change)
        {
            seg[v] = change;
            lazy[v] = change;
        }
        return;
    }
    push(v);

    int tm = (tl + tr) / 2;
    update(2 * v, tl, min(tm, tr), l, min(tm, r), change);
    update(2 * v + 1, max(tm + 1, tl), tr, max(l, tm + 1), r, change);

    seg[v] = max(seg[v * 2], seg[v * 2 + 1]);
}

pair<ll, ll> get(int v, int tl, int tr, int pos)
{
    if(tl == tr)
        return seg[v];

}*/

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

        for (pair<ll, ll> e : beginr[day])
        {
            curr.insert({-e.first, e.second});
        }
        pair<ll, ll> maxi;
        if (curr.size() > 0)
            maxi = *(curr.begin());
        else
            maxi = {0, day};
        // if (day == 5)
        // cout << maxi.first << " " << maxi.second << "\n";
        cout << -maxi.first + day - maxi.second << " ";
    }
    cout << "\n";
}

• Subtask 1: 0 / 100