/ SeriousOJ /

Record Detail

Time Exceeded


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 764.0 KiB
#2 Accepted 2ms 532.0 KiB
#3 Accepted 37ms 808.0 KiB
#4 Accepted 109ms 588.0 KiB
#5 Accepted 536ms 728.0 KiB
#6 Time Exceeded ≥2100ms ≥1.465 MiB
#7 Accepted 1821ms 2.496 MiB
#8 Accepted 749ms 1.02 MiB
#9 Accepted 843ms 1.809 MiB
#10 Accepted 870ms 2.422 MiB
#11 Accepted 858ms 6.594 MiB
#12 Accepted 559ms 6.133 MiB
#13 Time Exceeded ≥2099ms ≥22.805 MiB

Code

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

struct Node {
    int value; // Holds the aggregated value for the node
    int 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<int(int, int)> 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, int 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]
    int 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;
        int leftResult = query(node->left, l, mid, q_l, q_r);
        int 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<int(int, int)> combine)
        : startRange(startRange), endRange(endRange), combine(combine) {
        root = nullptr;
    }

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

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

    // Public query method
    int 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]

ll SUM = 0;
void solve() {
    int n;
    cin >> n;
    SUM += n;
    ImplicitLazySegmentTree st1(0, 1e9 + 4, [](int a, int 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(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;
        // 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;
    SUM += tc;
    // assert(1 <= tc && tc <= 5000);
    for (int t = 1; t <= tc; t++) {
        // cout << "Case " << t << ": ";
        solve();
        // assert(SUM <= 200000);
    }
    return 0;
}

Information

Submit By
Type
Submission
Problem
P1185 Segment
Language
C++17 (G++ 13.2.0)
Submit At
2025-03-24 21:28:24
Judged At
2025-03-24 21:28:24
Judged By
Score
75
Total Time
≥2100ms
Peak Memory
≥22.805 MiB