/ SeriousOJ /

Record Detail

Time Exceeded


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 532.0 KiB
#2 Accepted 1ms 532.0 KiB
#3 Wrong Answer 22ms 576.0 KiB
#4 Accepted 52ms 636.0 KiB
#5 Accepted 276ms 936.0 KiB
#6 Accepted 576ms 1.387 MiB
#7 Accepted 560ms 2.086 MiB
#8 Accepted 311ms 1.27 MiB
#9 Accepted 270ms 2.086 MiB
#10 Accepted 309ms 2.77 MiB
#11 Accepted 267ms 8.391 MiB
#12 Accepted 279ms 7.344 MiB
#13 Accepted 478ms 30.586 MiB
#14 Accepted 836ms 30.816 MiB
#15 Accepted 558ms 36.812 MiB
#16 Accepted 578ms 37.457 MiB
#17 Time Exceeded ≥2100ms ≥2.066 MiB

Code

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

struct Node {
    ll value; // Holds the aggregated value for the node
    ll lazy; // Lazy propagation value
    
    Node *left, *right;
    Node() : value(0), lazy(0), left(nullptr), right(nullptr) {}
};

class ImplicitLazySegmentTree {
private:
    Node* root;
    int startRange, endRange; // Define the logical range of the segment st1
    function<ll(ll, ll)> combine; // Combiner function (e.g., sum, max, min)

    // Push lazy updates down to children
    void propagate(Node*& node, int l, int r) {
        if (!node || node->lazy == 0) return;

        node->value += node->lazy * (r - l + 1); // Apply the lazy value

        // Propagate to children if not a leaf
        if (l != r) {
            if (!node->left) node->left = new Node();
            if (!node->right) node->right = new Node();

            node->left->lazy += node->lazy;
            node->right->lazy += node->lazy;
        }

        node->lazy = 0; // Clear the lazy value for the current node
    }

    // Update range [q_l, q_r] by adding `val`
    void update(Node*& node, int l, int r, int q_l, int q_r, ll val) {
        if (!node) node = new Node();
        propagate(node, l, r);

        if (l > r || q_r < l || q_l > r) return; // No overlap

        if (q_l <= l && r <= q_r) { // Total overlap
            node->lazy += val;
            propagate(node, l, r);
            return;
        }

        // Partial overlap
        int mid = (l + r) >> 1;
        update(node->left, l, mid, q_l, q_r, val);
        update(node->right, mid + 1, r, q_l, q_r, val);

        node->value = combine(
            node->left ? node->left->value : 0,
            node->right ? node->right->value : 0
        );
    }

    // Query the range [q_l, q_r]
    ll query(Node* node, int l, int r, int q_l, int q_r) {
        if (!node || l > r || q_r < l || q_l > r) return 0; // No overlap

        propagate(node, l, r);

        if (q_l <= l && r <= q_r) return node->value; // Total overlap

        // Partial overlap
        int mid = (l + r) >> 1;
        ll leftResult = query(node->left, l, mid, q_l, q_r);
        ll rightResult = query(node->right, mid + 1, r, q_l, q_r);

        return combine(leftResult, rightResult);
    }

    // Cleanup allocated nodes
    void cleanup(Node*& node) {
        if (!node) return;

        cleanup(node->left);
        cleanup(node->right);
        delete node;
        node = nullptr;
    }

public:
    // Constructor
    ImplicitLazySegmentTree(int startRange, int endRange, function<ll(ll, ll)> combine)
        : startRange(startRange), endRange(endRange), combine(combine) {
        root = nullptr;
    }

    // Destructor
    ~ImplicitLazySegmentTree() {
        cleanup(root);
    }

    // Public update method
    void update(int q_l, int q_r, ll val) {
        update(root, startRange, endRange, q_l, q_r, val);
    }

    // Public query method
    ll query(int q_l, int q_r) {
        return query(root, startRange, endRange, q_l, q_r);
    }
};
// Example usage: Range sum segment st1 with range [-1e9, 1e9]

void solve() {
    int n;
    cin >> n;
    ImplicitLazySegmentTree st1(0, 1e9 + 4, [](ll a, ll b) { return a + b; });
    // assert(1 <= n && n <= 200000);
    vector<pair<int, int>> v(n);
    for(auto &[l, r]: v) {
        cin >> l >> r;
        // assert(1 <= l && l <= 1000000000);
        // assert(1 <= r && r <= 1000000000);
        // assert(l <= r);
        st1.update(l, r, +1);
    }
    sort(v.begin(), v.end(), [&](auto x, auto y) {
        if(x.second == y.second) return x.first >= y.first;
        return x.second < y.second;
    });
    set<int> ans;
    int last = -1;
    for(auto &[l, r]: v) {
        if(last < l) {
            last = l;
        }
        else {
            if(last >= r) {
                if(st1.query(l, r) == 0) {
                    cout << "nO" << endl;
                    return;
                }
                int lo = l, hi = r, mid, point = -1;
                while(lo <= hi) {
                    mid = lo + hi >> 1;

                    if(st1.query(l, mid)) {
                        point = mid;
                        hi = mid - 1;
                    }
                    else lo = mid + 1;
                }
                if(point == -1) {
                    cout << "No" << endl;
                    return;
                }
                last = point;
            }
            else last++;
        }
        // cout << l << " " << r << " = " << last << endl;
        st1.update(last, last, -st1.query(last, last));
        ans.insert(last);
        last = *ans.rbegin();
    }
    if(ans.size() != n) {
        cout << "No" << endl;
        return;
    }
    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;
    // assert(1 <= tc && tc <= 5000);
    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-24 21:19:05
Judged At
2025-03-24 21:19:05
Judged By
Score
89
Total Time
≥2100ms
Peak Memory
≥37.457 MiB