oj.uz

Submission #1015402

# Submission time Handle Problem Language Result Execution time Memory
1015402 2024-07-06T10:14:25 Z keler RMQ (NOI17_rmq) C++14
0 / 100
 0 ms 600 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:num){
        // cout<<x<<" "<<y<<endl;
        if (cur!=x.first && cur!=-1){
            if (!an){
            while (n--) cout<<"-1"<<" ";
            return 0; 
        }
            an=0;
        }
        auto it=ang.lower_bound(x.first);
        if (it==ang.end()){
            while (n--){
                cout<<"-1"<<" ";
            }
            return 0; 
        }
        cur=x.first;
        if (*it==x.first) an=1;
        x.first=*it;
        // cout<<*it<<" "<<y<<endl;
        ang.erase(*it);
    }
    vector<int>ans(n);
    for (auto x:num) ans[x.second]=x.first;
    for (auto x:ans)cout<<x<<' ';
}

Subtask #1
0.0 / 23.0

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

Subtask #2
0.0 / 44.0

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

Subtask #3
0.0 / 33.0

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