#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 + 1), r(q + 1), x(q + 1);
for(int i = 1; i <= q; i++) {
std::cin >> l[i] >> r[i] >> x[i];
l[i] += 1;
r[i] += 1;
x[i] += 1;
}
std::vector<int> b(n + 1, 1);
for(int i = 1; i <= q; i++) {
for(int j = l[i]; j <= r[i]; j++) {
b[j] = std::max(b[j], x[i]);
}
}
std::vector<std::pair<int, int>> intervals[n + 1];
for(int i = 1; i <= q; i++) {
intervals[x[i]].push_back({l[i], r[i]});
}
std::vector<std::pair<int, int>> Do[n + 1];
int can = 1;
for(int it = 1; it <= n; it++) {
int L = - 1, R = n + 1;
for(auto [ll, rr] : intervals[it]) {
L = std::max(L, ll);
R = std::min(R, rr);
}
if(L > R) {
can = 0;
break;
}
Do[L].push_back({R, it});
}
if(!can) {
for(int i = 1; i <= n; i++) {
std::cout << - 1 << " ";
}
return 0;
}
std::vector<int> any(n + 1);
std::vector<int> a(n + 1, - 1);
for(int i = 1; i <= n; i++) {
std::sort(Do[i].begin(), Do[i].end());
for(auto [rr, xx] : Do[i]) {
for(int j = i; j <= rr; j++) {
if(!any[j] && b[j] == xx) {
any[j] = 1;
a[j] = xx;
break;
}
}
}
}
std::vector<int> was(n + 1);
for(int i = 1; i <= n; i++) {
if(a[i] != - 1) {
was[a[i]] = 1;
}
}
int curr = n;
std::vector<std::pair<int, int>> other;
for(int i = 1; i <= n; i++) {
if(a[i] == - 1) {
other.push_back({b[i], i});
}
}
std::sort(other.rbegin(), other.rend());
for(int it = 0; it < other.size(); it++) {
while(was[curr]) {
curr--;
}
if(b[other[it].second] > curr) {
can = 0;
break;
}
a[other[it].second] = curr--;
}
if(!can) {
for(int i = 1; i <= n; i++) {
std::cout << - 1 << " ";
}
return 0;
}
for(int i = 1; i <= q; i++) {
int mn = n + 1;
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 = 1; i <= n; i++) {
std::cout << - 1 << " ";
}
return 0;
}
for(int i = 1; i <= n; i++) {
std::cout << --a[i] << " ";
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |