/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 540.0 KiB
#2 Accepted 1ms 540.0 KiB
#3 Accepted 7ms 788.0 KiB
#4 Accepted 15ms 820.0 KiB
#5 Accepted 115ms 956.0 KiB
#6 Accepted 70ms 1.109 MiB
#7 Accepted 94ms 1.312 MiB
#8 Accepted 89ms 952.0 KiB
#9 Accepted 124ms 1.672 MiB
#10 Accepted 132ms 2.242 MiB
#11 Accepted 176ms 5.223 MiB
#12 Accepted 190ms 6.559 MiB
#13 Accepted 924ms 32.133 MiB
#14 Accepted 870ms 16.316 MiB
#15 Accepted 879ms 16.191 MiB
#16 Accepted 928ms 16.863 MiB
#17 Accepted 637ms 12.863 MiB
#18 Accepted 32ms 624.0 KiB
#19 Accepted 111ms 1.5 MiB
#20 Accepted 2ms 332.0 KiB
#21 Accepted 17ms 540.0 KiB
#22 Accepted 22ms 772.0 KiB
#23 Accepted 256ms 21.633 MiB
#24 Accepted 651ms 13.484 MiB
#25 Accepted 273ms 22.332 MiB
#26 Accepted 296ms 25.02 MiB

Code

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// *st.find_by_order(k): K-th element in a set (counting from zero).
// st.order_of_key(k): Number of items strictly smaller than k. (same as lower_bound of k)
// less_equal<T> => for ordered_multiset or, ordered_multimap

void solve() {
    int n;
    cin >> n;
    map<int, vector<pair<int, int>>> mp; // {r, {{l, pos}};
    for(int i = 1; i <= n; i++) {
        int l, r;
        cin >> l >> r;
        mp[r].push_back({l, i});
    }
    ordered_set<int> ans;
    ans.insert(INT_MAX);
    for(auto &[r, vec]: mp) {
        sort(vec.begin(), vec.end());
        for(auto &[l, pos]: vec) {
            int k = ans.order_of_key(l);
            auto it = ans.find_by_order(k);
            if(it == ans.end() or l < *it) {
                ans.insert(l);
            }
            else { // *it == l
                int lo = 1, hi = int(ans.size()) - k - 1, mid, point = -1;
                while(lo <= hi) {
                    mid = lo + hi >> 1;
                    if(*ans.find_by_order(k + mid) != l + mid) {
                        point = l + mid;
                        hi = mid - 1;
                    }
                    else lo = mid + 1;
                } 
                if(point > r) {
                    cout << "nO" << endl;
                    return;
                }
                ans.insert(point);
            }
        }
    }
    ans.erase(INT_MAX);
    cout << "yEs" << endl;
    for(auto &i: ans) cout << i << " ";
    cout << endl;
    return;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int tc = 1;
    cin >> tc;
    for (int t = 1; t <= tc; t++) {
        // cout << "Case " << t << ": ";
        solve();
    }
    return 0;
}

Information

Submit By
Type
Submission
Problem
P1185 Segment
Language
C++17 (G++ 13.2.0)
Submit At
2025-03-29 19:19:55
Judged At
2025-03-29 19:19:55
Judged By
Score
100
Total Time
928ms
Peak Memory
32.133 MiB