oj.uz

Submission #1015374

# Submission time Handle Problem Language Result Execution time Memory
1015374 2024-07-06T09:48:37 Z keler RMQ (NOI17_rmq) C++14
0 / 100
 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<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()) num[i]=pq.top().first;
    }
    // for (auto x:num)cout<<x<<" ";
    // cout<<endl;
    for (auto &x:num){
        auto it=ang.lower_bound(x);

        if (it==ang.end()){
            while (n--){
                cout<<"-1"<<" ";
            }
            return 0; 
        }

        x=*it;
        ang.erase(*it);
    }
    for (auto x:num)cout<<x<<" ";
}

Subtask #1
0.0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -