Submission #515541

#	Time	Username	Problem	Language	Result	Execution time	Memory
515541		Joo	RMQ (NOI17_rmq)	C++17	0 / 100	3 ms	5196 KiB

rmq

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

const int N  = 1e5+10;

int n, Q, ans[N];
set<int> rem_pos, rem_val;
vector<pair<int, int>> pre_in[N];
pair<int, int> in[N];
bool ok = true;

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

int main(void){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> Q;
    for(int i = 1 ; i <= Q; i++){
        int l, r, v; cin >> l >> r >> v;
        l++, r++, v++;

        pre_in[v].emplace_back(l, r);
    
    }
    
    for(int i = 1; i <= n; i++){
        rem_pos.insert(i);
        rem_val.insert(i);
    }

    for(int i = 1; i <= n; i++){
        in[i] = {-1, -1};
        if(pre_in[i].empty()) continue;
        
        sort(pre_in[i].begin(), pre_in[i].end());
        
        auto [l, r] = pre_in[i][0];
        for(int j = 1; j < pre_in[i].size(); j++){
            if(pre_in[i][j].first > r){
                ok = false;
            }

            r = min(r, pre_in[i][j].second);
            l = max(l, pre_in[i][j].first);
        }

        if(r-l+1 > n-i+1){
            ok = false;
        }

        in[i] = {l, r};
    }

    // for(int i = 1; i <= n; i++){
    //     cout << "I " << i << " : " << in[i].first << ", " << in[i].second << "\n";
    // }

    if(!ok) ex();

    for(int i = n; i >= 1; i--){
        auto [el, er] = in[i];
        if(el == -1) continue;

        auto itl = rem_pos.lower_bound(el);
        if(itl == rem_pos.end() or *itl > er){
            ex();
        }

        assert(rem_val.find(i) != rem_val.end());
        if(rem_val.find(i) == rem_val.end()) ex();

        ans[*itl] = i;
        int tmp1 = *itl;
        itl++;
        rem_pos.erase(tmp1);
        rem_val.erase(i);

        // cout << "CUR " << i << " : ";
        while(itl != rem_pos.end() and *itl <= er){
            auto itv = rem_val.end();

            assert(itv != rem_val.begin());

            --itv;

            // cout << *itv << " ";
            assert(*itv > i);
            if(*itv <= i){
                ex();
            }

            ans[*itl] = *(itv);

            tmp1 = *itl;
            itl++;
            rem_pos.erase(tmp1);
            rem_val.erase(itv);
        }
        // cout << "\n";
    }

    if(!ok) ex();

    for(int i = 1; i <= n; i++){
        if(ans[i] == 0){
            ans[i] = *(rem_val.begin());
            rem_val.erase(rem_val.begin());
        }
    }

    for(int i = 1; i <= n; i++){
        cout << ans[i]-1 << " ";
    }
    cout << "\n";

    return 0;
}

Compilation message (stderr)

rmq.cpp: In function 'int main()':
rmq.cpp:41:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for(int j = 1; j < pre_in[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~~~~~~

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