제출 #1199150

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1199150		Hanksburger	거래 (IZhO13_trading)	C++20	100 / 100	300 ms	30068 KiB

trading

#include <bits/stdc++.h>
#define int long long
using namespace std;
struct node
{
    node *lc, *rc;
    int l, r, val;
    node(int l, int r) : lc(0), rc(0), l(l), r(r), val(-1e18) {}
} *root;
void build(node *i)
{
    if (i->l==i->r)
        return;
    int mid=(i->l+i->r)/2;
    i->lc=new node(i->l, mid);
    i->rc=new node(mid+1, i->r);
    build(i->lc);
    build(i->rc);
}
void upd(node *i, int ql, int qr, int x)
{
    if (ql<=i->l && i->r<=qr)
    {
        i->val=max(i->val, x);
        return;
    }
    int mid=(i->l+i->r)/2;
    if (i->l<=qr && ql<=mid)
        upd(i->lc, ql, qr, x);
    if (mid<qr && ql<=i->r)
        upd(i->rc, ql, qr, x);
}
int qry(node *i, int x)
{
    if (i->l==i->r)
        return i->val;
    int mid=(i->l+i->r)/2;
    if (x<=mid)
        return max(i->val, qry(i->lc, x));
    return max(i->val, qry(i->rc, x));
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    root=new node(1, n);
    build(root);
    for (int i=1; i<=m; i++)
    {
        int l, r, x;
        cin >> l >> r >> x;
        upd(root, l, r, x-l);
    }
    for (int i=1; i<=n; i++)
        cout << max(0LL, qry(root, i)+i) << ' ';
}

• Subtask 1: 100 / 100