제출 #1037062

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1037062		vjudge1	거래 (IZhO13_trading)	C++17	100 / 100	172 ms	60220 KiB

trading

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define For(i, a, b) for (int i = a; i <= b; ++i)
#define RFor(i, a, b) for (int i = a; i >= b; --i)
#define get_bit(bit, mask) (((mask) >> (bit)) & 1)
#define set_bit(bit, mask) (mask |= (1ll << bit))
#define top_bit(mask) (31 - __builtin_clz(mask))
#define log(a) cout << #a << " = " << a << '\n'
#define ii pair<int, int>
#define iii tuple<int, int, int>

const int N = 5e5 + 5;

int ans[N];

int n, m;
int l[N], r[N], x[N];

void GetInput() {
    cin >> n >> m;
    For(i, 1, m) cin >> l[i] >> r[i] >> x[i];
}

void Rep() {
    For(i, 1, n) cout << ans[i] << ' ';
}

vector<int> add[N], trash[N];
void Solve() {
    For(i, 1, m) 
        add[l[i]].push_back(l[i] - x[i]),
        trash[r[i]].push_back(l[i] - x[i]);
    multiset<int> mts;
    For(i, 1, n) {
        int lans = 0;

        for (int item : add[i]) mts.insert(item);
        if (mts.size()) lans = i - *mts.begin();

        ans[i] = lans;

        for (int item : trash[i]) mts.erase(mts.find(item));
    }
}

signed main() {
#ifndef LOCAL
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif
    // int t; cin >> t;
    // while (t--)
        GetInput(),
        Solve(),
        Rep();
}

• Subtask 1: 100 / 100