Submission #1301006

#TimeUsernameProblemLanguageResultExecution timeMemory
1301006baotoan655Long Mansion (JOI17_long_mansion)C++20
100 / 100
173 ms41308 KiB
#include <bits/stdc++.h>
#define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
using namespace std;

const int N = 5e5 + 5;
int n, q;
vector<int> a[N];
int c[N];
int le[N], ri[N], cur[N];
pair<int, int> pos[N];

bool chk(int dir, int id, pair<int, int> x) {
    if(id < 1 || id > n) return false;
    if(dir == 0) return x.first <= ri[id] && ri[id] <= x.second;
    return x.first <= le[id] && le[id] <= x.second;
}
pair<int, int> operator + (const pair<int, int> &x, const pair<int, int> &y) {
    return make_pair(min(x.first, y.first), max(x.second, y.second));
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

//    file("A") else file("task");

    cin >> n;
    for(int i = 1; i < n; ++i) cin >> c[i];
    for(int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        a[i].resize(x);
        for(int j = 0; j < x; ++j) cin >> a[i][j];
    }
    memset(cur, -1, sizeof cur);

    for(int i = 1; i < n; i++) {
        for(int x : a[i]) cur[x] = i;
        le[i + 1] = cur[c[i]];
    }

    memset(cur, 0x3f, sizeof cur);

    for(int i = n; i > 1; i--) {
        for(int x : a[i]) cur[x] = i;
        ri[i - 1] = cur[c[i - 1]];
    }

    for(int i = 1; i <= n; i++) {
        pos[i] = make_pair(i, i);
        while(true) {
            bool trai = chk(0, pos[i].first - 1, pos[i]);
            if(trai) pos[i] = pos[i] + pos[pos[i].first - 1];
            bool phai = chk(1, pos[i].second + 1, pos[i]);
            if(phai) pos[i].second++;
            if(!trai && !phai) break;
        }
    }
    cin >> q;
    while(q--) {
        int x, y;
        cin >> x >> y;
        if(pos[x].first <= y && y <= pos[x].second) cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...