제출 #1177507

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1177507		ducanh0811	Long Mansion (JOI17_long_mansion)	C++20	0 / 100	550 ms	22908 KiB

long_mansion

#include <bits/stdc++.h>
#define fi          first
#define se          second
using namespace std;

int n;
#define MAXN 500005
int c[MAXN];
vector<int> a[MAXN];
int F[MAXN];
int G[MAXN];
int track[MAXN];
int pref[MAXN];
int suff[MAXN];

struct SMT{
    int n;
    vector<pair<int,int>> st;
    SMT(int _n = 0) : n(_n) {
        st.assign((n << 2) + 5, make_pair(0, 0));
    }
    void up(int id, int l, int r, int p, pair<int,int> val){
        if (p < l || r < p) return;
        if (l == r) return st[id] = val, void();
        int mid = (l + r) >> 1;
        up(id << 1, l, mid, p, val);
        up(id << 1 | 1, mid + 1, r, p, val);
        st[id].fi = max(st[id << 1].fi, st[id << 1 | 1].fi);
        st[id].se = min(st[id << 1].se, st[id << 1 | 1].se);
    }
    void up(int p, pair<int,int> val){
        up(1, 1, n, p, val);
    }
    int getMAX(int id, int l, int r, int u, int v){
        if (v < l || r < u) return 0;
        if (u <= l && r <= v) return st[id].fi;
        int mid = (l + r) >> 1;
        return max(getMAX(id<<1,l,mid,u,v), getMAX(id<<1|1,mid+1,r,u,v));
    }
    int getMAX(int u, int v){
        return getMAX(1, 1, n, u, v);
    }
    int getMIN(int id, int l, int r, int u, int v){
        if (v < l || r < u) return 1e9;
        if (u <= l && r <= v) return st[id].se;
        int mid = (l + r) >> 1;
        return min(getMIN(id<<1,l,mid,u,v), getMIN(id<<1|1,mid+1,r,u,v));
    }
    int getMIN(int u, int v){
        return getMIN(1, 1, n, u, v);
    }
};

void solve(){
    cin >> n;
    for (int i = 1; i < n; ++i) cin >> c[i];
    for (int i = 1; i <= n; ++i){
        int m; cin >> m;
        for (int j = 1; j <= m; ++j){
            int x; cin >> x;
            a[i].push_back(x);
        }
    }
    for (int i = 0; i <= n; ++i) track[i] = n + 1;
    for (int i = n; i >= 1; --i){
        F[i] = track[c[i]];
        for (int &x : a[i]) track[x] = i;
    }
    for (int i = 0; i <= n; ++i) track[i] = 0;
    for (int i = 1; i <= n; ++i){
        G[i] = track[c[i-1]];
        for (int &x : a[i]) track[x] = i;
    }
    SMT tree(n);
    for (int i = 1; i <= n; ++i) tree.up(i, make_pair(F[i], G[i]));
    for (int i = 1; i <= n; ++i) pref[i] = suff[i] = i;
    for (int i = 2; i <= n; ++i){
        int lo = 1, hi = i - 1, pos = i;
        while (lo <= hi){
            int mid = (lo + hi) >> 1;
            if (tree.getMAX(mid, i - 1) <= i){
                pos = mid;
                hi = mid - 1;
            } else lo = mid + 1;
        }
        pref[i] = pos;
    }
    for (int i = n - 1; i >= 1; --i){
        int lo = i + 1, hi = n, pos = i;
        while (lo <= hi){
            int mid = (lo + hi) >> 1;
            if (tree.getMIN(i + 1, mid) >= i){
                pos = mid;
                lo = mid + 1;
            } else hi = mid - 1;
        }
        suff[i] = pos;
    }
    int q; cin >> q;
    for (int i = 1; i <= q; ++i){
        int x, y; cin >> x >> y;
        if (x < y){
            if (pref[x] <= tree.getMIN(x + 1, y)){
                cout << "YES" << '\n';
            } else cout << "NO" << '\n';
        } else {
            swap(x, y);
            if (suff[y] >= tree.getMAX(x, y - 1)){
                cout << "YES" << '\n';
            } else cout << "NO" << '\n';
        }
    }
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    solve();
    return 0;
}

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