提出 #25433137

---

ソースコード 拡げる

#include <bits/stdc++.h>
#include <atcoder/segtree>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++(i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++(i))
#define REP_R(i, n) for (int i = (int)(n)-1; (i) >= 0; --(i))
#define REP3R(i, m, n) for (int i = (int)(n)-1; (i) >= (int)(m); --(i))
#define ALL(x) ::std::begin(x), ::std::end(x)
using namespace std;

int op(int a, int b) { return a + b; }
int e() { return 0; }

std::vector<int> solve(int64_t n, int m, const std::vector<int64_t> &l, const std::vector<int64_t> &r, const std::vector<int64_t> &x) {
    vector<vector<int>> from_l(n);
    vector<vector<int>> from_r(n + 1);
    REP (i, m) {
        from_l[l[i]].push_back(i);
        from_r[r[i]].push_back(i);
    }

    atcoder::segtree<int, op, e> segtree(n);
    set<int> unused;
    REP (i, n) {
        unused.insert(i);
    }
    unused.insert(1e9);
    REP (r, n + 1) {
        for (int i : from_r[r]) {
            while (segtree.prod(l[i], r) < x[i]) {
                int j = *prev(unused.lower_bound(r));
                segtree.set(j, 1);
                unused.erase(j);
            }
        }
    }

    vector<int> ans(n);
    REP (i, n) {
        ans[i] = segtree.get(i);
    }
    return ans;
}

// generated by oj-template v4.8.0 (https://github.com/online-judge-tools/template-generator)
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int64_t N;
    int M;
    std::cin >> N >> M;
    std::vector<int64_t> L(M), R(M), X(M);
    REP (i, M) { std::cin >> L[i] >> R[i] >> X[i]; -- L[i]; }
    auto ans = solve(N, M, L, R, X);
    REP (i, (int)ans.size()) { std::cout << ans[i] << ' '; }
    std::cout << '\n';
    return 0;
}

提出情報

ジャッジ結果