| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 537395 |
2022-03-15T04:24:23 Z |
ac2hu |
RMQ (NOI17_rmq) |
C++14 |
|
56 ms |
7992 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];
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(it,end);
}
}
// 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";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
0 ms |
340 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
0 ms |
340 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
1 ms |
340 KB |
Output is correct |
| 13 |
Correct |
1 ms |
340 KB |
Output is correct |
| 14 |
Correct |
1 ms |
340 KB |
Output is correct |
| 15 |
Correct |
1 ms |
340 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
1 ms |
340 KB |
Output is correct |
| 19 |
Correct |
1 ms |
340 KB |
Output is correct |
| 20 |
Correct |
1 ms |
340 KB |
Output is correct |
| 21 |
Correct |
1 ms |
340 KB |
Output is correct |
| 22 |
Correct |
1 ms |
340 KB |
Output is correct |
| 23 |
Correct |
1 ms |
340 KB |
Output is correct |
| 24 |
Correct |
1 ms |
340 KB |
Output is correct |
| 25 |
Correct |
0 ms |
340 KB |
Output is correct |
| 26 |
Correct |
0 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
0 ms |
340 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
1 ms |
340 KB |
Output is correct |
| 13 |
Correct |
1 ms |
340 KB |
Output is correct |
| 14 |
Correct |
1 ms |
340 KB |
Output is correct |
| 15 |
Correct |
1 ms |
340 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
1 ms |
340 KB |
Output is correct |
| 19 |
Correct |
1 ms |
340 KB |
Output is correct |
| 20 |
Correct |
1 ms |
340 KB |
Output is correct |
| 21 |
Correct |
1 ms |
340 KB |
Output is correct |
| 22 |
Correct |
1 ms |
340 KB |
Output is correct |
| 23 |
Correct |
1 ms |
340 KB |
Output is correct |
| 24 |
Correct |
1 ms |
340 KB |
Output is correct |
| 25 |
Correct |
0 ms |
340 KB |
Output is correct |
| 26 |
Correct |
0 ms |
340 KB |
Output is correct |
| 27 |
Correct |
45 ms |
5460 KB |
Output is correct |
| 28 |
Correct |
47 ms |
7372 KB |
Output is correct |
| 29 |
Correct |
49 ms |
7028 KB |
Output is correct |
| 30 |
Correct |
48 ms |
7784 KB |
Output is correct |
| 31 |
Correct |
37 ms |
6020 KB |
Output is correct |
| 32 |
Correct |
39 ms |
6008 KB |
Output is correct |
| 33 |
Correct |
34 ms |
6476 KB |
Output is correct |
| 34 |
Correct |
21 ms |
4436 KB |
Output is correct |
| 35 |
Correct |
35 ms |
7500 KB |
Output is correct |
| 36 |
Correct |
41 ms |
7992 KB |
Output is correct |
| 37 |
Correct |
56 ms |
7964 KB |
Output is correct |
| 38 |
Correct |
24 ms |
5052 KB |
Output is correct |
| 39 |
Correct |
43 ms |
7060 KB |
Output is correct |
| 40 |
Correct |
0 ms |
340 KB |
Output is correct |
| 41 |
Correct |
0 ms |
340 KB |
Output is correct |
