#include <bits/stdc++.h>
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, q;
std::cin >> n >> q;
std::vector<int> l(q), r(q), x(q);
for(int i = 0; i < q; i++) {
std::cin >> l[i] >> r[i] >> x[i];
}
std::vector<int> b(n);
for(int i = 0; i < q; i++) {
for(int j = l[i]; j <= r[i]; j++) {
b[j] = std::max(b[j], x[i]);
}
}
std::vector<int> pos(n, - 1);
for(int i = 0; i < n; i++) {
if(pos[b[i]] == - 1) {
pos[b[i]] = i;
}
}
std::vector<int> a(n, - 1);
for(int i = 0; i < n; i++) {
if(pos[i] != - 1) {
a[pos[i]] = i;
}
}
std::vector<std::pair<int, int>> ops;
for(int i = 0; i < n; i++) {
if(a[i] != - 1) {
continue;
}
ops.push_back({b[i], i});
}
std::sort(ops.begin(), ops.end());
std::reverse(ops.begin(), ops.end());
int curr = n - 1;
for(int i = 0; i < ops.size(); i++) {
a[ops[i].second] = curr--;
}
int can = 1;
std::vector<int> was(n);
for(int i = 0; i < n; i++) {
if(was[a[i]]) {
can = 0;
}
was[a[i]] = 1;
}
for(int i = 0; i < q; i++) {
int mn = n;
for(int j = l[i]; j <= r[i]; j++) {
mn = std::min(mn, a[j]);
}
if(mn != x[i]) {
can = 0;
}
}
if(!can) {
for(int i = 0; i < n; i++) {
a[i] = - 1;
}
}
for(int i = 0; i < n; i++) {
std::cout << a[i] << " ";
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |