Submission #1264116

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264116		aihoi	Long Mansion (JOI17_long_mansion)	C++20	0 / 100	205 ms	20096 KiB

long_mansion

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
using ll = long long;

// Cách 2: segment tree + memo trên các đoạn [l,r]
// Input giống code gốc. Không giả sử K <= 20.

struct SegMin {
    int n;
    vector<int> st;
    void build(const vector<int>& a) {
        n = (int)a.size() - 1; // a is 1..n-1
        st.assign(4*(n+5), INT_MAX);
        build_rec(1,1,n,a);
    }
    void build_rec(int p,int l,int r,const vector<int>& a){
        if(l==r){ st[p]=a[l]; return; }
        int m=(l+r)/2;
        build_rec(p<<1,l,m,a);
        build_rec(p<<1|1,m+1,r,a);
        st[p]=min(st[p<<1], st[p<<1|1]);
    }
    // find first index in [ql,qr] with value < threshold. return -1 if none.
    int find_first_less(int ql,int qr,int threshold){
        if(ql>qr || n==0) return -1;
        return find_rec(1,1,n,ql,qr,threshold);
    }
    int find_rec(int p,int l,int r,int ql,int qr,int thresh){
        if(ql>r || qr<l) return -1;
        if(st[p] >= thresh) return -1;
        if(l==r) return l;
        int m=(l+r)/2;
        int res = find_rec(p<<1,l,m,ql,qr,thresh);
        if(res!=-1) return res;
        return find_rec(p<<1|1,m+1,r,ql,qr,thresh);
    }
};

struct SegMax {
    int n;
    vector<int> st;
    void build(const vector<int>& a) {
        n = (int)a.size() - 1; // a is 1..n-1
        st.assign(4*(n+5), INT_MIN);
        build_rec(1,1,n,a);
    }
    void build_rec(int p,int l,int r,const vector<int>& a){
        if(l==r){ st[p]=a[l]; return; }
        int m=(l+r)/2;
        build_rec(p<<1,l,m,a);
        build_rec(p<<1|1,m+1,r,a);
        st[p]=max(st[p<<1], st[p<<1|1]);
    }
    // find last index in [ql,qr] with value > threshold. return -1 if none.
    int find_last_greater(int ql,int qr,int threshold){
        if(ql>qr || n==0) return -1;
        return find_rec(1,1,n,ql,qr,threshold);
    }
    int find_rec(int p,int l,int r,int ql,int qr,int thresh){
        if(ql>r || qr<l) return -1;
        if(st[p] <= thresh) return -1;
        if(l==r) return l;
        int m=(l+r)/2;
        // search right child first to get last index
        int res = find_rec(p<<1|1,m+1,r,ql,qr,thresh);
        if(res!=-1) return res;
        return find_rec(p<<1,l,m,ql,qr,thresh);
    }
};

int n, q;
vector<int> req; // 1..n-1
vector<vector<int>> rooms; // 1..n

// memo map: key = (ll)l<<32 | r  -> value pair(finalL, finalR)
unordered_map<unsigned long long, pair<int,int>> mp;
SegMin segMin;
SegMax segMax;

inline unsigned long long key_lr(int l,int r){
    return ( (unsigned long long)l << 32 ) | (unsigned long long)r;
}

pair<int,int> expand_interval(int l,int r){
    unsigned long long k0 = key_lr(l,r);
    if(mp.find(k0)!=mp.end()) return mp[k0];

    vector<unsigned long long> visited;
    int curL = l, curR = r;

    while(true){
        unsigned long long curk = key_lr(curL, curR);
        if(mp.find(curk)!=mp.end()){
            // found cached result for this exact state
            auto res = mp[curk];
            for(auto vk: visited) mp[vk] = res;
            return res;
        }
        visited.push_back(curk);

        // try expand right: find first corridor i >= curR with last_pos[i] < curL
        int start = curR; // corridor indices start..n-1
        int i = -1;
        if(start <= n-1) i = segMin.find_first_less(start, n-1, curL);
        int newR = (i == -1 ? n : i);
        if(newR > curR){
            curR = newR;
            continue; // try again
        }

        // try expand left: find last corridor i <= curL-1 with first_pos[i] > curR
        int end = curL - 1;
        int j = -1;
        if(end >= 1) j = segMax.find_last_greater(1, end, curR);
        int newL = (j == -1 ? 1 : j+1);
        if(newL < curL){
            curL = newL;
            continue;
        }

        // neither side expanded
        break;
    }

    pair<int,int> ans = {curL, curR};
    for(auto vk: visited) mp[vk] = ans;
    return ans;
}

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

    if(!(cin >> n)) return 0;
    req.assign(n+1, 0);
    for(int i=1;i<=n-1;i++) cin >> req[i];
    rooms.assign(n+1, {});
    int totalKeys = 0;
    for(int i=1;i<=n;i++){
        int b; cin >> b;
        totalKeys += b;
        rooms[i].resize(b);
        for(int j=0;j<b;j++) cin >> rooms[i][j];
    }

    // Coordinate compress key ids (because key ids can be large)
    vector<int> allkeys;
    allkeys.reserve(totalKeys + n);
    for(int i=1;i<=n;i++) for(int x: rooms[i]) allkeys.push_back(x);
    for(int i=1;i<=n-1;i++) allkeys.push_back(req[i]);
    sort(allkeys.begin(), allkeys.end());
    allkeys.erase(unique(allkeys.begin(), allkeys.end()), allkeys.end());
    auto getid = [&](int x){
        return (int)(lower_bound(allkeys.begin(), allkeys.end(), x) - allkeys.begin());
    };
    // remap
    for(int i=1;i<=n;i++) for(auto &x: rooms[i]) x = getid(x);
    for(int i=1;i<=n-1;i++) req[i] = getid(req[i]);
    int K = (int)allkeys.size();

    // compute last_pos[i] = last occurrence position <= i of key req[i]
    vector<int> lastOcc(K, 0);
    vector<int> last_pos(n+1, 0); // 1..n-1
    for(int p=1;p<=n;p++){
        for(int x: rooms[p]) lastOcc[x] = p;
        if(p <= n-1) last_pos[p] = lastOcc[ req[p] ];
    }
    // compute first_pos[i] = first occurrence position >= i+1 of key req[i]
    vector<int> nextOcc(K, n+1);
    vector<int> first_pos(n+1, n+1);
    for(int p=n;p>=1;p--){
        for(int x: rooms[p]) nextOcc[x] = p;
        if(p <= n-1) first_pos[p] = nextOcc[ req[p] ];
    }

    // build segment trees on corridors 1..n-1
    if(n-1 >= 1){
        // last_pos: if no occurrence -> 0. first_pos: if none -> n+1
        segMin.build(last_pos);
        segMax.build(first_pos);
    } else {
        // handle trivial small n: our code expects seg trees to be valid
        // leave them empty (they handle n==0 case)
    }

    cin >> q;
    while(q--){
        int l,r; cin >> l >> r;
        if(l <= r){
            auto res = expand_interval(l,l);
            if(res.second >= r) cout << "YES\n"; else cout << "NO\n";
        } else {
            auto res = expand_interval(l,l);
            if(res.first <= r) cout << "YES\n"; else cout << "NO\n";
        }
    }
    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 15
• Subtask 4: 0 / 75