Submission #431566

#TimeUsernameProblemLanguageResultExecution timeMemory
431566lycLong Mansion (JOI17_long_mansion)C++14
10 / 100
3047 ms47688 KiB
#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef pair<ll,ll> pll;

const int mxN = 5e5+5;

int N, C[mxN], Q;
set<int> keys[mxN];
int k2[mxN];
int goleft[mxN], goright[mxN];

void mergeto(set<int>& a, set<int>& b) {
    if (SZ(a) > SZ(b)) swap(a,b);
    for (auto& x : a) b.insert(x);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> N;
    FOR(i,1,N-1){
        cin >> C[i];
    }
    C[0] = C[N] = 1e9+5; // impossible
    FOR(i,1,N){
        int B; cin >> B;
        FOR(j,1,B){
            int A; cin >> A;
            keys[i].insert(A);
            k2[i] |= (1<<A);
        }
    }

    if (N <= 5000) {
        FOR(i,1,N){
            set<int> k;
            for (auto& x : keys[i]) k.insert(x);
            goleft[i] = goright[i] = i;
            while (true) {
                if (k.count(C[goleft[i]-1])) {
                    --goleft[i];
                    for (auto& x : keys[goleft[i]]) k.insert(x);
                } else if (k.count(C[goright[i]])) {
                    ++goright[i];
                    for (auto& x : keys[goright[i]]) k.insert(x);
                } else break;
            }
        }
    } else {
        FOR(i,1,N){
            goleft[i] = goright[i] = i;
            while (true) {
                if (goleft[i] > 1 && (k2[i] & (1<<C[goleft[i]-1]))) {
                    --goleft[i];
                    k2[i] |= k2[goleft[i]];
                    goleft[i] = goleft[goleft[i]];
                    goright[i] = max(goright[i], goright[i]);
                } else if (goright[i] < N && (k2[i] & (1<<C[goright[i]]))) {
                    ++goright[i];
                    k2[i] |= k2[goright[i]];
                } else break;
            }
        }
    }

    cin >> Q;
    FOR(i,1,Q){
        int X, Y; cin >> X >> Y;
        cout << (goleft[X] <= Y && Y <= goright[X] ? "YES" : "NO") << '\n';
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...