Submission #1015402

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015402		keler	RMQ (NOI17_rmq)	C++14	0 / 100	0 ms	600 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<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 / 23
• Subtask 2: 0 / 44
• Subtask 3: 0 / 33