Submission #1015374

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015374		keler	RMQ (NOI17_rmq)	C++14	0 / 100	0 ms	348 KiB

rmq

#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 / 23
• Subtask 2: 0 / 44
• Subtask 3: 0 / 33