# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1015396 |
2024-07-06T10:08:19 Z |
keler |
RMQ (NOI17_rmq) |
C++14 |
|
0 ms |
348 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define int long long
#define inf LLONG_MAX
#define pb push_back
#define lc 2*pos+1
#define rc 2*pos+2
#define halleluya ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
signed main(){
halleluya
int n,q;cin>>n>>q;
vector<pair<int,int>>rm[n];
for (int i=1;i<=q;i++){
int l,r,x;cin>>l>>r>>x;
rm[l].pb({x,r});
}
set<int>ang;
for (int i=0;i<n;i++) ang.insert(i);
vector<pair<int,int>>num(n);
priority_queue<pair<int,int>>pq;
for (int i=0;i<n;i++){
if (pq.size()){
while (pq.top().second<i){
pq.pop();
if (pq.empty()) break;
}
}
if (rm[i].size()){
for (auto x:rm[i]){
pq.push({x.first,x.second});
}
}
if (pq.size()){
// cout<<pq.top().first<<" "<<i<<endl;
num[i].first=pq.top().first;
num[i].second=i;
}
}
// for (auto x:num)cout<<x<<" ";
// cout<<endl;
sort(num.begin(),num.end(),greater<pair<int,int>>());
int cur=-1;
bool an=0;
for (auto &[x,y]:num){
// cout<<x<<" "<<y<<endl;
if (cur!=x && cur!=-1){
if (!an){
while (n--) cout<<"-1"<<" ";
return 0;
}
an=0;
}
auto it=ang.lower_bound(x);
if (it==ang.end()){
while (n--){
cout<<"-1"<<" ";
}
return 0;
}
cur=x;
if (*it==x) an=1;
x=*it;
// cout<<*it<<" "<<y<<endl;
ang.erase(*it);
}
vector<int>ans(n);
for (auto [x,y]:num) ans[y]=x;
for (auto x:ans)cout<<x<<' ';
}
Compilation message
rmq.cpp: In function 'int main()':
rmq.cpp:47:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
47 | for (auto &[x,y]:num){
| ^
rmq.cpp:70:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
70 | for (auto [x,y]:num) ans[y]=x;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |