제출 #110101

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
110101		Frankenween	거래 (IZhO13_trading)	C++17	100 / 100	281 ms	37084 KiB

trading

#include <bits/stdc++.h>


//#define _FORTIFY_SOURCE 0
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("no-stack-protector")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define ull unsigned long long
#define pii pair<ll, ll>
#define mp make_pair
#define ll long long
#define ld long double
#define pb push_back
#define deb(x) cout << #x << " = " << x << endl
#define all(x) x.begin(), x.end()
#define vi vector<ll>

const ll mod = (ll)1e9 + 7;
const ll inf = (ll)1e18;
const long double e = 2.718281828459;
const long double pi = atan2l(0, -1);


using namespace std;


template <class T>
istream& operator>>(istream &in, vector<T> &arr) {
    for (T &cnt : arr) {
        in >> cnt;
    }
    return in;
};


struct stree {
    vector<ll> t, upd;

    stree(ll n) {
        t.resize(4 * n, -inf);
        upd.resize(4 * n, -inf);
    }

    void push(ll v, ll d) {
        if (upd[v] == -inf) {
            return;
        }
        t[v] = upd[v];
        if (d != 0) {
            upd[v * 2] = upd[v];
            upd[v * 2 + 1] = upd[v];
        }
        upd[v] = -inf;
    }

    void update(ll v, ll l, ll r, ll ql, ll qr, ll val) {
        push(v, r - l);
        if (ql <= l and r <= qr) {
            upd[v] = val;
            push(v, r - l);
            return;
        }
        if (ql > r or qr < l) {
            return;
        }
        ll mid = (l + r) / 2;
        update(v * 2, l, mid, ql, qr, val);
        update(v * 2 + 1, mid + 1, r, ql, qr, val);
    }

    ll get(ll v, ll l, ll r, ll pos) {
        push(v, r - l);
        if (l == r) {
            return t[v];
        }
        ll mid = (l + r) / 2;
        if (pos <= mid) {
            return get(v * 2, l, mid, pos);
        } else {
            return get(v * 2 + 1, mid + 1, r, pos);
        }
    }
};


void solve() {
    ll n, m;
    cin >> n >> m;
    stree t(n);
    vector<pair<ll, pair<ll, ll>>> q;
    for (int i = 0; i < m; i++) {
        ll l, r, x;
        cin >> l >> r >> x;
        l--;
        r--;
        x -= l;
        q.pb({x, {l, r}});
    }
    sort(all(q));
    for (int i = 0; i < m; i++) {
        t.update(1, 0, n - 1, q[i].second.first, q[i].second.second, q[i].first);
    }
    for (int i = 0; i < n; i++) {
        ll val = t.get(1, 0, n - 1, i);
        if (val == -inf) {
            cout << "0 ";
        } else {
            cout << i + val << " ";
        }
    }
}


int main() {
#ifndef LOCAL
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#else
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    cout.precision(30);
    srand(time(0));
    cout.setf(ios::fixed);
    solve();
    return 0;
}

• Subtask 1: 100 / 100