| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 868377 | lamter | RMQ (NOI17_rmq) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#define ILOVEU "VERIFY.INP"#define ULOVEI "VERIFY.OUT"#include <bits/stdc++.h>template <class T>using min_priority_queue = std::priority_queue <T, std::vector <T>, std::greater <T>>;template <class T, class ff = std::function <T (T, T)>>class SparseTable {private: int n, n_log; std::vector <std::vector <T>> mat; ff f;public: SparseTable(const std::vector <T>& a, const ff& _f) : f(_f) { n = (int) a.size(); n_log = (int) 32 - __builtin_clz(n); mat.resize(n_log); mat[0] = a; for (int j = 1; j < n_log; j += 1) { mat[j].resize(n - (1 << j) + 1); for (int i = 0; i <= n - (1 << j); i += 1) mat[j][i] = f(mat[j - 1][i], mat[j - 1][i + (1 << (j - 1))]); } } T get(int l, int r) const { int j = 31 - __builtin_clz(r - l + 1); return f(mat[j][l], mat[j][r - (1 << j) + 1]); }};const int inf = 1E9 + 7;class segtree {private: int n; std::vector <std::pair <int, int>> tree; std::vector <int> lazy; void build(int x, int l, int r) { if (l == r) { tree[x] = {0, l}; return; } int m = (l + r) / 2; int y = x + ((m - l + 1) << 1); build(x + 1, l, m); build(y, m + 1, r); tree[x] = std::min(tree[x + 1], tree[y]); } void push(int x, int y) { if (not lazy[x]) return; lazy[x + 1] += lazy[x]; lazy[y] += lazy[x]; tree[x + 1].first += lazy[x]; tree[y].first += lazy[x]; lazy[x] = 0; } void update(int x, int l, int r, int ll, int rr, int v) { if (l > r or ll > rr or ll > r or l > rr) return; if (ll <= l and r <= rr) { tree[x].first += v; lazy[x] += v; return; } int m = (l + r) / 2; int y = x + ((m - l + 1) << 1); push(x, y); update(x + 1, l, m, ll, rr, v); update(y, m + 1, r, ll, rr, v); tree[x] = std::min(tree[x + 1], tree[y]); } std::pair <int, int> get(int x, int l, int r, int ll, int rr) { if (l > r or ll > rr or ll > r or l > rr) return std::make_pair(inf, inf); if (ll <= l and r <= rr) return tree[x]; int m = (l + r) / 2; int y = x + ((m - l + 1) << 1); push(x, y); return std::min(get(x + 1, l, m, ll, rr), get(y, m + 1, r, ll, rr)); }public: segtree(int _n = 0) : n(_n) { int sz = 2 * n - 1; tree.resize(sz); lazy.assign(sz, 0); build(0, 0, n - 1); } void update(int l, int r, int v) { update(0, 0, n - 1, l, r, v); } std::pair <int, int> get(int l, int r) { return get(0, 0, n - 1, l, r); }};int main(void) { if (fopen(ILOVEU, "r")) { freopen(ILOVEU, "r", stdin); freopen(ULOVEI, "w", stdout); } std::ios_base::sync_with_stdio(0); std::cin.tie(nullptr); int n, Q; std::cin >> n >> Q; std::vector <std::array <int, 2>> inter(n, {0, n - 1}); std::vector <std::array <int, 2>> onion(n, {n - 1, 0}); std::vector <std::tuple <int, int, int>> conds(Q); std::vector <bool> free(n, 1); for (int q = 0; q < Q; q += 1) { int l, r, x; std::cin >> l >> r >> x; inter[x] = {std::max(l, inter[x][0]), std::min(r, inter[x][1])}; onion[x] = {std::min(l, onion[x][0]), std::max(r, onion[x][1])}; conds[q] = {l, r, x}; free[x] = 0; } auto solve = [&] (void) -> std::vector <int> { for (int i = 0; i < n; i += 1) if (inter[i][0] > inter[i][1]) return std::vector <int> (n, -1); std::vector <int> a(n); segtree sgt(n); for (int i = 0; i < n; i += 1) if (not free[i]) sgt.update(onion[i][0], onion[i][1], +1); for (int i = 0; i < n; i += 1) { if (not free[i]) sgt.update(onion[i][0], onion[i][1], -1); int p, has; std::tie(has, p) = sgt.get(inter[i][0], inter[i][1]); if (has) return std::vector <int> (n, -1); sgt.update(p, p, inf); a[p] = i; } SparseTable spt(a, [&] (int nguoi_dan_ong_tham_lam_chinh_la, int anh) -> int { return std::min(nguoi_dan_ong_tham_lam_chinh_la, anh); }); for (const auto& [l, r, x] : conds) { if (spt.get(l, r) != x) return std::vector <int> (n, -1); } return a; }; std::vector <int> res = solve(); for (int x : res) std::cout << x << ' '; return 0^0;}