Submission #515859

#	Time	Username	Problem	Language	Result	Execution time	Memory
515859		Joo	RMQ (NOI17_rmq)	C++17	100 / 100	71 ms	11648 KiB

rmq

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5+10;

int n, Q, Li[N], Lu[N], Ri[N], Ru[N], ans[N];
set<int> rem_pos, rem_val;

void ex(){
    for(int i = 0; i < n; i++) cout << "-1 ";
    exit(0);
}

int main(void){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> Q;
    for(int i = 0; i < n; i++){
        Li[i] = Ru[i] = -1e9;
        Lu[i] = Ri[i] = 1e9;        
        rem_pos.insert(i);
        rem_val.insert(i);
    }

    for(int i = 0; i < Q; i++){
        int l, r, x; cin >> l >> r >> x;
        Li[x] = max(Li[x], l), Ri[x] = min(Ri[x], r);
        Lu[x] = min(Lu[x], l), Ru[x] = max(Ru[x], r);
    }    

    for(int i = n-1; i >= 0; i--){
        if(Li[i] == -1e9) continue;
        if(Li[i] > Ri[i]) ex();
        
        auto itp = rem_pos.lower_bound(Li[i]);
        if(itp == rem_pos.end() or *itp > Ri[i]) ex();

        ans[*itp] = i;
        rem_pos.erase(itp), rem_val.erase(i);

        while(!rem_pos.empty()){
            itp = rem_pos.lower_bound(Lu[i]);
            if(itp == rem_pos.end() or *itp > Ru[i]) break;

            int v = *(rem_val.rbegin());
            if(v < i) ex();

            ans[*itp] = v;
            rem_pos.erase(itp), rem_val.erase(v);
        }
    }

    while(!rem_pos.empty()){
        ans[*(rem_pos.begin())] = *rem_val.begin();
        rem_pos.erase(rem_pos.begin()), rem_val.erase(rem_val.begin());
    }

    for(int i = 0; i < n; i++) cout << ans[i] << " ";
    cout << "\n";

    return 0;
}

• Subtask 1: 23 / 23
• Subtask 2: 44 / 44
• Subtask 3: 33 / 33