| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 537381 |
2022-03-15T04:09:05 Z |
ac2hu |
RMQ (NOI17_rmq) |
C++14 |
|
1 ms |
212 KB |
#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];
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};
}
auto merge = [&](pair<int,int> a,pair<int,int> b) -> pair<int,int>{
return {min(a.first,b.first), max(a.second,b.second)};
// LARGEST RANGE WHERE IT IS MINIMUM
};
for(int _ = 0;_<m;_++){
int l,r,a;cin >> l >> r >> a;
if(seq[a].first == -1){
seq[a] = {l,r};
}
else
seq[a] = merge(seq[a], {l,r});
}
for(int i = 0;i<n;i++){
if(seq[i].second < seq[i].first){
for(int i= 0;i<n;i++){
cout << -1 << " ";
}
exit(0);
}
}
// deb(i,seq[i]);
set<int> s;
for(int i = 0;i<n;i++)
s.insert(i);
vector<int> not_selected;
for(int i = n - 1;i>=0;i--){
if(seq[i].first == -1)
not_selected.push_back(i);
else{
bool sel = false;
auto it = s.lower_bound(seq[i].first);
// --it;
auto end = s.upper_bound(seq[i].second);
set<int> temp1 = s;
for(auto tt = it;tt != end;++tt){
if(!sel){
sel = true;
ans[*tt] = i;
}
uq[*tt] = max(i, uq[*tt]);
temp1.erase(temp1.find(*tt));
}
if(!sel){
for(int i= 0;i<n;i++)
cout << -1 << " ";
exit(0);
}
swap(temp1,s);
}
}
// 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){
for(int i= 0;i<n;i++)
cout << -1 << " ";
exit(0);
}
ans[temp.back()] = i;
temp.pop_back();
}
}
for(int i =0 ;i<n;i++)
cout << ans[i] << " ";
cout << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
