Submission #1303907

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303907		chaitanyamehta	Curtains (NOI23_curtains)	C++20	60 / 100	1603 ms	362712 KiB

curtains

// Compile with: g++ -std=c++17 -O2 curtains_subtask5.cpp -o curtains
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
using vi = vector<int>;
struct Node {
    vector<pair<int,int>> intervals; // (l, r) sorted by r
    vector<int> prefix_hole;  // size = intervals.size(), hole values
    vector<int> prefix_reach; // size = intervals.size(), reach values
};

struct SegTree {
    int n;
    vector<Node> st;
    vector<vector<pair<int,int>>> start_at; // intervals starting at position i

    SegTree(int _n=0){ init(_n); }
    void init(int _n){
        n = _n;
        st.assign(4*n+5, Node());
        start_at.assign(n+2, {});
    }

    void add_interval_input(int l, int r){
        if(l<1 || l>n) return;
        start_at[l].push_back({l,r});
    }

    // build: merge children intervals and compute prefix arrays per node
    void build_all(int idx, int L, int R){
        if(L==R){
            auto &node = st[idx];
            node.intervals = start_at[L];
            sort(node.intervals.begin(), node.intervals.end(), [](auto &a, auto &b){
                if(a.second != b.second) return a.second < b.second;
                return a.first < b.first;
            });
        } else {
            int mid=(L+R)/2;
            build_all(idx*2, L, mid);
            build_all(idx*2+1, mid+1, R);
            // merge child intervals by r
            auto &left = st[idx*2].intervals;
            auto &right = st[idx*2+1].intervals;
            auto &nodeint = st[idx].intervals;
            nodeint.clear();
            nodeint.reserve(left.size() + right.size());
            std::merge(left.begin(), left.end(), right.begin(), right.end(),
                       back_inserter(nodeint),
                       [](const pair<int,int>&a, const pair<int,int>&b){
                           if(a.second != b.second) return a.second < b.second;
                           return a.first < b.first;
                       });
        }
        // compute prefix arrays for this node (DSU marks inside [L,R])
        auto &node = st[idx];
        int m = (int)node.intervals.size();
        node.prefix_hole.assign(m, 0);
        node.prefix_reach.assign(m, 0);
        if(m == 0) return; // nothing to do
        int len = R - L + 1;
        // DSU parent: parent[i] = largest uncovered index <= i (1-based within [L,R])
        vector<int> parent(len+1);
        for(int i=0;i<=len;i++) parent[i] = i;
        function<int(int)> findp = [&](int x)->int{
            if(x<=0) return 0;
            return parent[x]==x?x:parent[x]=findp(parent[x]);
        };
        int reach = R; // for empty prefix, reach = R (no extension beyond R)
        for(int i=0;i<m;i++){
            int l = node.intervals[i].first;
            int r = node.intervals[i].second;
            // update reach (furthest right covered by prefix)
            reach = max(reach, r);
            // mark covered positions inside [L,R]: cover [u,v]
            int u = max(l, L);
            int v = min(r, R);
            if(u <= v){
                int pos = findp(v - L + 1);
                while(pos > 0 && (L + pos - 1) >= u){
                    // mark pos as covered
                    parent[pos] = pos - 1;
                    pos = findp(pos);
                }
            }
            // compute hole: largest index inside [L,R] that is uncovered
            int last_uncovered = findp(len); // index in 1..len or 0
            int hole;
            if(last_uncovered == 0) hole = L - 1; // no hole inside
            else hole = L + last_uncovered - 1;
            node.prefix_hole[i] = hole;
            node.prefix_reach[i] = reach;
        }
    }

    // collect nodes fully inside [ql,qr]
    void collect_nodes(int idx, int L, int R, int ql, int qr, vector<tuple<int,int,int>> &out){
        if(ql > R || qr < L) return;
        if(ql <= L && R <= qr){
            out.emplace_back(idx, L, R);
            return;
        }
        int mid=(L+R)/2;
        collect_nodes(idx*2, L, mid, ql, qr, out);
        collect_nodes(idx*2+1, mid+1, R, ql, qr, out);
    }

    // combine two adjacent segments:
    // left covers [a,b], right covers [b+1,c]
    // left: (hole1, reach1), right: (hole2, reach2)
    // hole values use sentinel: hole = interval.L - 1 means no hole in that interval
    pair<int,int> combine_adjacent(const pair<int,int> &left, const pair<int,int> &right,
                                   int a, int b, int c){
        int hole1 = left.first, reach1 = left.second;
        int hole2 = right.first, reach2 = right.second;
        int hole, reach;
        if(hole1 >= a){
            // left has a hole inside [a,b] -> cannot be fixed by right
            hole = hole1;
        } else {
            // left has no hole inside [a,b]
            if(hole2 >= b+1){
                // right has a hole in [b+1,c]; left can fix it only if reach1 >= hole2
                if(reach1 >= hole2){
                    hole = a - 1; // fixed -> no hole
                } else {
                    hole = hole2;
                }
            } else {
                // right has no hole -> no hole overall
                hole = a - 1;
            }
        }
        reach = max(reach1, reach2);
        return {hole, reach};
    }

    // query: returns true if [s,e] can be exactly covered
    bool query(int s, int e){
        vector<tuple<int,int,int>> segs;
        collect_nodes(1,1,n,s,e,segs);
        if(segs.empty()) return false;
        // sort nodes left->right by their L
        sort(segs.begin(), segs.end(), [](auto &A, auto &B){
            return get<1>(A) < get<1>(B);
        });
        bool started = false;
        pair<int,int> cur; int curL=0, curR=0;
        for(auto &t : segs){
            int idx = get<0>(t), L = get<1>(t), R = get<2>(t);
            auto &node = st[idx];
            // find count of curtains with r <= e (binary search)
            int cnt = 0;
            if(!node.intervals.empty()){
                // node.intervals sorted by r
                int lo = 0, hi = (int)node.intervals.size(); // count = first index with r > e
                while(lo < hi){
                    int mid = (lo + hi) >> 1;
                    if(node.intervals[mid].second <= e) lo = mid + 1;
                    else hi = mid;
                }
                cnt = lo;
            }
            pair<int,int> nodeRes;
            if(cnt == 0){
                // empty prefix: hole = R (largest uncovered inside), reach = R (no extension)
                nodeRes = { R, R };
            } else {
                nodeRes = { node.prefix_hole[cnt-1], node.prefix_reach[cnt-1] };
            }
            if(!started){
                cur = nodeRes;
                curL = L; curR = R;
                started = true;
            } else {
                cur = combine_adjacent(cur, nodeRes, curL, curR, R);
                curR = R;
            }
        }
        // final check: if final hole < s then no hole inside [s,e]
        int final_hole = cur.first;
        return !(final_hole >= s && final_hole <= e);
    }
};


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#if 0
    // Example I/O format (replace with your problem format)
    // n m q
    // m lines: l r
    // q lines: s e
#endif
    int n, m, q;
    if(!(cin >> n >> m >> q)) return 0;
    SegTree st(n);
    for(int i=0;i<m;i++){
        int l,r; cin>>l>>r;
        if(l<1) l=1;
        if(r>n) r=n;
        if(l<=n && r>=1 && l<=r) st.add_interval_input(l,r);
    }
    st.build_all(1,1,n);
    while(q--){
        int s,e; cin >> s >> e;
        if(s<1) s=1;
        if(e>n) e=n;
        if(s>e){
            cout << "NO\n";
            continue;
        }
        bool ok = st.query(s,e);
        cout << (ok? "YES\n" : "NO\n");
    }
    return 0;
}

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