Submission #917514

#TimeUsernameProblemLanguageResultExecution timeMemory
917514406RMQ (NOI17_rmq)C++17
100 / 100
70 ms19148 KiB
#include <bits/stdc++.h> #define int int64_t #define FOR(i, a, b) for (int i = (a); i < (b); ++i) using namespace std; using ar = array<int, 2>; const int64_t INF = 1ll << 60; const int N = 1e5 + 5; vector<ar> delta[N]; int n, q, re[N], mx[N], L[N], R[N]; vector<int> M[N]; void imp() { FOR(i, 0, n) cout << "-1 "; exit(0); } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> q; fill(L, L + n, -1); fill(R, R + n, n); while (q--) { int l, r, x; cin >> l >> r >> x; L[x] = max(L[x], l); R[x] = min(R[x], r); delta[l].push_back({x, +1}); delta[r + 1].push_back({x, -1}); } multiset<int> S; vector<int> cur; FOR(i, 0, n) { for (auto [x, d]: delta[i]) { if (d == 1) S.insert(x); else S.erase(S.find(x)); } if (S.size()) mx[i] = *S.rbegin(), M[mx[i]].push_back(i); else cur.push_back(i); } FOR(i, 0, n) { int l = L[i], r = R[i]; if (l == -1) { if (cur.empty()) imp(); re[cur.back()] = i; cur.pop_back(); continue; } if (l > r || M[i].empty()) imp(); int x = -1; while (M[i].size()) { x = M[i].back(); M[i].pop_back(); if (l <= x && x <= r) break; cur.push_back(x); } if (!(l <= x && x <= r)) imp(); re[x] = i; for (auto t: M[i]) cur.push_back(t); } FOR(i, 0, n) cout << re[i] << ' '; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...