#include<bits/stdc++.h> using namespace std; #define file "a" // #define int long long #define ll long long #define pii pair<int, int> #define pli pair<ll, int> #define fi first #define se second #define sz(a) (int)a.size() #define pb push_back #define mask(i) (1 << i) const int N = 1e5, inf = 1e9; mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count()); int rad(int l, int r) { return l + rd() % (r - l + 1); } void MAX(int &a, int b) { a = max(a, b); } void MIN(int &a, int b) { a = min(a, b); } struct stt { int l, r, id; bool operator < (const stt &o) const { return id > o.id; } }; int n, q; int kq[N + 2], t[4 * N + 2], lim[N + 2], lz[4 * N + 2]; stt a[N + 2]; vector<pii> g[N + 2]; void down(int id) { if (lz[id] != 0) { MAX(t[id * 2], lz[id]); MAX(t[id * 2 + 1], lz[id]); MAX(lz[id * 2], lz[id]); MAX(lz[id * 2 + 1], lz[id]); lz[id] = 0; } } void update(int l, int r, int id, int u, int v, int x) { if (r < u || v < l) return; if (u <= l && r <= v) { MAX(t[id], x); MAX(lz[id], x); return; } down(id); int m = (l + r) / 2; update(l, m, id * 2, u, v, x); update(m + 1, r, id * 2 + 1, u, v, x); } int get(int l, int r, int id, int u) { if (l == r) return t[id]; down(id); int m = (l + r) / 2; if (u <= m) return get(l, m, id * 2, u); else return get(m + 1, r, id * 2 + 1, u); } void shutdown() { for (int i = 0; i < n; i++) cout << -1 << " "; } bool cmp(int a, int b) { return lim[a] < lim[b]; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if (fopen(file".inp", "r")) { freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout); } cin >> n >> q; memset(kq, -1, sizeof kq); for (int i = 1; i <= q; i++) { int l, r, id; cin >> l >> r >> id; g[id].pb({l, r}); update(0, n - 1, 1, l, r, id); } for (int i = 0; i < n; i++) lim[i] = get(0, n - 1, 1, i); set<int> st; for (int i = 0; i < n; i++) st.insert(i); vector<int> a1, a2; for (int i = n - 1; i >= 0; i--) { if (sz(g[i]) == 0) { a2.pb(i); continue; } int L = g[i][0].fi, R = g[i][0].se; for (int j = 1; j < sz(g[i]); j++) { int l = g[i][j].fi, r = g[i][j].se; if (R < l || r < L) { L = -1; break; } MAX(L, l); MIN(R, r); } if (L != -1) { set<int> :: iterator it; it = st.lower_bound(L); if (it == st.end() || *it > R) return shutdown(), 0; kq[*it] = i; } for (pii x : g[i]) { L = x.fi; R = x.se; set<int> :: iterator it; it = st.lower_bound(L); vector<set<int> :: iterator> del; while (it != st.end()) { if (*it > R) break; del.pb(it); it++; } for (set<int> :: iterator x : del) st.erase(x); } } for (int i = 0; i < n; i++) if (kq[i] == -1) a1.pb(i); sort(a1.begin(), a1.end(), cmp); sort(a2.begin(), a2.end()); for (int i = 0; i < sz(a1); i++) { if (lim[a1[i]] > a2[i]) return shutdown(), 0; kq[a1[i]] = a2[i]; } for (int i = 0; i < n; i++) cout << kq[i] << " "; }

rmq.cpp: In function 'int main()':
rmq.cpp:77:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |     freopen(file".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
rmq.cpp:78:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |     freopen(file".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~