제출 #1096962

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1096962		vladilius	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	627 ms	131700 KiB

long_mansion

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define arr3 array<int, 3>

struct ST{
    vector<pii> t;
    vector<int> a;
    int n;
    ST(int ns){
        n = ns;
        t.resize(4 * n);
        a.resize(n + 1);
    }
    void upd(int v, int tl, int tr, int& p, int& x){
        if (tl == tr){
            t[v] = {x, x};
            return;
        }
        int tm = (tl + tr) / 2, vv = 2 * v;
        if (p <= tm){
            upd(vv, tl, tm, p, x);
        }
        else {
            upd(vv + 1, tm + 1, tr, p, x);
        }
        t[v].ff = min(t[vv].ff, t[vv + 1].ff);
        t[v].ss = max(t[vv].ss, t[vv + 1].ss);
    }
    void upd(int p, int x){
        upd(1, 1, n, p, x);
        a[p] = x;
    }
    vector<arr3> all;
    void dec(int v, int tl, int tr, int& l, int& r){
        if (l > tr || r < tl) return;
        if (l <= tl && tr <= r){
            all.pb({v, tl, tr});
            return;
        }
        int tm = (tl + tr) / 2, vv = 2 * v;
        dec(vv, tl, tm, l, r);
        dec(vv + 1, tm + 1, tr, l, r);
    }
    int fn1(int v, int tl, int tr, int& x){
        if (tl == tr) return (tl - (a[tl] <= x));
        int tm = (tl + tr) / 2, vv = 2 * v;
        if (t[vv + 1].ss > x){
            return fn1(vv + 1, tm + 1, tr, x);
        }
        return fn1(vv, tl, tm, x);
    }
    int find1(int l, int r, int x){
        if (l > r || a[r] > x) return -1;
        all.clear();
        dec(1, 1, n, l, r);
        reverse(all.begin(), all.end());
        for (auto [v, tl, tr]: all){
            if (t[v].ss > x){
                return fn1(v, tl, tr, x) + 1;
            }
        }
        return l;
    }
    int fn2(int v, int tl, int tr, int& x){
        if (tl == tr) return tl + (a[tl] >= x);
        int tm = (tl + tr) / 2, vv = 2 * v;
        if (t[vv].ff < x){
            return fn2(vv, tl, tm, x);
        }
        return fn2(vv + 1, tm + 1, tr, x);
    }
    int find2(int l, int r, int x){
        if (l > r || a[l] < x) return -1;
        all.clear();
        dec(1, 1, n, l, r);
        for (auto [v, tl, tr]: all){
            if (t[v].ff < x){
                return fn2(v, tl, tr, x) - 1;
            }
        }
        return r;
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n; cin>>n;
    vector<int> c(n);
    for (int i = 1; i < n; i++){
        cin>>c[i];
    }
    
    vector<int> A[n + 1];
    for (int i = 1; i <= n; i++){
        int x; cin>>x;
        while (x--){
            int y; cin>>y;
            A[i].pb(y);
        }
    }
    
    vector<int> x(n), lst(n + 1, n + 1);
    for (int i = n; i > 0; i--){
        if (i < n){
            x[i] = lst[c[i]];
        }
        for (int j: A[i]){
            lst[j] = i;
        }
    }
    
    fill(lst.begin(), lst.end(), 0);
    vector<int> y(n);
    for (int i = 1; i < n; i++){
        for (int j: A[i]){
            lst[j] = i;
        }
        y[i] = lst[c[i]];
    }
    
    ST T1(n - 1), T2(n - 1);
    for (int i = 1; i < n; i++){
        T1.upd(i, x[i]);
        T2.upd(i, y[i]);
    }
    
    map<pii, pii> mp;
    function<pii(int, int)> solve = [&](int l, int r){
        auto it = mp.find({l, r});
        if (it != mp.end()) return (*it).ss;
        int l1 = l, r1 = r;
        bool ind1 = 0, ind2 = 0;
        int j = T1.find1(1, l - 1, r);
        if (j != -1){
            l = j;
            ind1 = 1;
        }
        j = T2.find2(r, n - 1, l);
        if (j != -1){
            r = j + 1;
            ind2 = 1;
        }
        
        if (!ind1 && !ind2){
            mp[{l, r}] = {l, r};
            return make_pair(l, r);
        }
        pii x = solve(l, r);
        mp[{l1, r1}] = x;
        return x;
    };

    vector<pii> rr(n + 1);
    for (int i = 1; i <= n; i++){
        solve(i, i);
        rr[i] = mp[{i, i}];
    }
    
    int Q; cin>>Q;
    while (Q--){
        int x, y; cin>>x>>y;
        cout<<((rr[x].ff <= y && y <= rr[x].ss) ? "YES" : "NO")<<"\n";
    }
}

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