#include <bits/stdc++.h>
#ifdef DEBUG
#include "../templates/debug.h"
#else
#define deb(x...)
#endif
using namespace std;
const int N = 1e5 + 10;
int n,m;
int ans[N], uq[N];
pair<int,int> seq[N];
pair<int,int> fseq[N];
void kill(){
for(int i= 0;i<n;i++){
cout << -1 << " ";
}
exit(0);
}
signed main() {
iostream::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
cin >> n >> m;
for(int i =0 ;i<n;i++){
ans[i] = -1;
seq[i] = {-1,-1};
fseq[i] = {-1,-1};
}
for(int _ = 0;_<m;_++){
int l,r,a;cin >> l >> r >> a;
if(seq[a].first == -1){
seq[a] = {l,r};
fseq[a] = {l,r};
}
else{
fseq[a] = {max(fseq[a].first,l), min(fseq[a].second,r)};
seq[a] = {min(seq[a].first,l), max(seq[a].second, r)};
}
}
set<int> s;
for(int i = 0;i<n;i++)
s.insert(i);
for(int i = n - 1;i>=0;i--){
if(seq[i].first != -1){
auto temp = s.lower_bound(fseq[i].first);
if(temp == s.end() || *temp > fseq[i].second){
kill();
}
else{
uq[*temp] = i;
ans[*temp] = i;
s.erase(temp);
}
auto it = s.lower_bound(seq[i].first);
// --it;
auto end = s.upper_bound(seq[i].second);
for(auto tt = it;tt != end;++tt){
uq[*tt] = i;
s.erase(tt++);
}
}
}
// for(int i =0;i<n;i++)
// cout << ans[i] << " ";
// cout << "\n";
vector<int> temp;
for(int i =0;i<n;i++){
if(ans[i] == -1)
temp.push_back(i);
}
sort(temp.begin(),temp.end(),[&](int a,int b){
return uq[a] < uq[b];
});
deb(temp);
// cout << temp.back() << "\n";
for(int i = n - 1;i>=0;i--){
if(seq[i].first == -1){
if(uq[temp.back()] > i){
kill();
}
ans[temp.back()] = i;
temp.pop_back();
}
}
for(int i =0 ;i<n;i++)
cout << ans[i] << " ";
cout << "\n";
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
