Submission #1146940

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146940		atharva_a_b	Curtains (NOI23_curtains)	C++17	9 / 100	1596 ms	11132 KiB

curtains

#include <iostream>
#include <vector>
#include <set>

class segment_tree {
    int32_t n;
    std::vector<int32_t> lazy;
    std::vector<int32_t> tree;

    void do_set(int32_t v, int32_t l, int32_t r, const int32_t& sl, const int32_t& sr, const int32_t& val) {
        if(l > r) return;

        int32_t lc = (2*v)+1, rc = (2*v)+2, mid = l+((r-l)/2);

        if(lazy[v] != -1) {
            tree[v] = lazy[v];
            if(l != r) {
                lazy[lc] = lazy[v];
                lazy[rc] = lazy[v];
            }
            lazy[v] = -1;
        }

        if(l > sr || r < sl) return; // no overlap

        if(sl <= l && r <= sr) { // total overlap
            tree[v] = val;
            if(l != r) {
                lazy[lc] = val;
                lazy[rc] = val;
            }
            return;
        }

        // partial overlap

        do_set(lc, l, mid, sl, sr, val);
        do_set(rc, mid+1, r, sl, sr, val);

        tree[v] = std::min(tree[lc], tree[rc]);
    }

    int32_t do_query(int32_t v, int32_t l, int32_t r, const int32_t& ql, const int32_t& qr) {
        if(l > r) return INT32_MAX;

        int32_t lc = (2*v)+1, rc = (2*v)+2, mid = l+((r-l)/2);

        if(lazy[v] != -1) {
            tree[v] = lazy[v];
            if(l != r) {
                lazy[lc] = lazy[v];
                lazy[rc] = lazy[v];
            }
            lazy[v] = -1;
        }

        if(l > qr || r < ql) return INT32_MAX; // no overlap

        if(ql <= l && r <= qr) { // total overlap
            return tree[v];
        }

        // partial overlap

        return std::min(do_query(lc, l, mid, ql, qr), do_query(rc, mid+1, r, ql, qr));
    }

public:
    segment_tree(const int32_t& in_n) : n(in_n), lazy(4*in_n, -1), tree(4*in_n, 0) {}

    void set(const int32_t& sl, const int32_t& sr, const int32_t& val) {
        do_set(0, 0, n-1, sl, sr, val);
    }

    int32_t query(const int32_t& ql, const int32_t& qr) {
        return do_query(0, 0, n-1, ql, qr);
    }
};

bool intersects(const int32_t& l1, const int32_t& r1, const int32_t& l2, const int32_t& r2);
bool enclosed(const int32_t& l, const int32_t& r, const int32_t& el, const int32_t& er);

int main(void) {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int32_t n, m, q;
    std::cin >> n >> m >> q;

    int32_t l, r, s, e;
    std::vector<std::set<int32_t>> ends_of_start(n);
    std::vector<std::set<int32_t>> starts_of_end(n);

    while(m--) {
        std::cin >> l >> r;
        --l, --r;
        ends_of_start[l].insert(r);
        starts_of_end[r].insert(l);
    }

    // for(int32_t i = 0; i < n; ++i) {
    //     std::cout << i << ": ";
    //     for(auto& end: ends_of_start[i]) {
    //         std::cout << end << " ";
    //     }
    //     std::cout << "\n";
    // }

    // for(int32_t i = 0; i < n; ++i) {
    //     std::cout << i << ": ";
    //     for(auto& start: starts_of_end[i]) {
    //         std::cout << start << " ";
    //     }
    //     std::cout << "\n";
    // }

    segment_tree st(n);

    while(q--) {
        std::cin >> s >> e;
        --s, --e;
        if(ends_of_start[s].empty() || starts_of_end[e].empty()) {
            std::cout << "NO\n";
            continue;
        }

        auto it1 = ends_of_start[s].upper_bound(e), it2 = starts_of_end[e].lower_bound(s);
        if(it1 == ends_of_start[s].begin() || it2 == starts_of_end[e].end()) {
            std::cout << "NO\n";
            continue;
        }

        --it1;
        if((*it1) == e) {
            std::cout << "YES\n";
            continue;
        }

        l = (*it1)+1;
        r = (*it2)-1;

        if(l > r) {
            std::cout << "YES\n";
            continue;
        } 

        for(int32_t i = 0; i < n; ++i) {
            for(auto& end: ends_of_start[i]) {
                if(intersects(i, end, l, r) && enclosed(i, end, s, e)) {
                    st.set(std::max(i, l), std::min(end, r), 1);
                }
            }
        }

        if(st.query(l, r) == 1) {
            std::cout << "YES\n";
        } else {
            std::cout << "NO\n";
        }

        st.set(l, r, 0);
    }

    return 0;
}

bool intersects(const int32_t& l1, const int32_t& r1, const int32_t& l2, const int32_t& r2) {
    if(l1 <= l2) {
        return (l2 <= r1);
    } else {
        return (l1 <= r2);
    }
}

bool enclosed(const int32_t& l, const int32_t& r, const int32_t& el, const int32_t& er) {
    return (el <= l && r <= er);
}

• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 0 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 36
• Subtask 6: 0 / 20