Submission #854332

#	Time	Username	Problem	Language	Result	Execution time	Memory
854332		DAleksa	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	1442 ms	132656 KiB

long_mansion

#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 10, LOG = 20;
int n, q;
int need[N];
int c[N];
vector<int> keys[N];
int L[N], R[N];
int prv[N], nxt[N];
int lst[N];
int st_prv[N][LOG], st_nxt[N][LOG];

int get_prv(int l, int r) {
    if(l > r) return INT_MAX;
    int len = r - l + 1;
    int bit = 31 - __builtin_clz(len);
    return min(st_prv[l][bit], st_prv[r - (1 << bit) + 1][bit]);
}

int get_nxt(int l, int r) {
    if(l > r) return 0;
    int len = r - l + 1;
    int bit = 31 - __builtin_clz(len);
    return max(st_nxt[l][bit], st_nxt[r - (1 << bit) + 1][bit]);
}

int find_left(int start, int target) {
    int l = 1, r = start;
    int ans = r;
    while(l <= r) {
        int mid = (l + r) / 2;
        if(get_nxt(mid, start - 1) <= target) {
            ans = mid;
            r = mid - 1;
        } else l = mid + 1;
    }
    return ans;
}

int find_right(int target, int start) {
    int l = start, r = n;
    int ans = l;
    while(l <= r) {
        int mid = (l + r) / 2;
        if(get_prv(start, mid - 1) >= target) {
            ans = mid;
            l = mid + 1;
        } else r = mid - 1;
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for(int i = 1; i < n; i++) cin >> need[i];
    for(int i = 1; i <= n; i++) {
        cin >> c[i];
        keys[i].resize(c[i]);
        for(int j = 0; j < c[i]; j++) cin >> keys[i][j];
    }
    for(int i = 1; i < n; i++) {
        for(int j : keys[i]) lst[j] = i;
        prv[i] = lst[need[i]];
    }
    for(int i = 0; i < N; i++) lst[i] = n + 1;
    for(int i = n; i > 1; i--) {
        for(int j : keys[i]) lst[j] = i;
        nxt[i - 1] = lst[need[i - 1]];
    }
    for(int i = 1; i < n; i++) {
        st_prv[i][0] = prv[i];
        st_nxt[i][0] = nxt[i];
    }
    for(int j = 1; j < LOG; j++) {
        for(int i = 1; i + (1 << (j - 1)) < n; i++) {
            st_prv[i][j] = min(st_prv[i][j - 1], st_prv[i + (1 << (j - 1))][j - 1]);
            st_nxt[i][j] = max(st_nxt[i][j - 1], st_nxt[i + (1 << (j - 1))][j - 1]);
        }
    }
    L[1] = 1;
    R[1] = find_right(1, 1);
    for(int i = 2; i <= n; i++) {
        L[i] = R[i] = i;
        if(R[i - 1] == i - 1) {
            R[i] = find_right(i, i);
            while(true) {
                int temp = find_left(L[i], R[i]);
                if(temp == L[i]) break;
                L[i] = temp;
                temp = find_right(L[i], R[i]);
                if(temp == R[i]) break;
                R[i] = temp;
            }
        } else {
            R[i] = find_right(i, i);
            L[i] = find_left(i, R[i]);
            if(L[i] < i) {
                L[i] = L[i - 1];
                R[i] = R[i - 1];
            }
        }
    }
    int q;
    cin >> q;
    while(q--) {
        int l, r;
        cin >> l >> r;
        cout << ((L[l] <= r && r <= R[l]) ? "YES\n" : "NO\n");
    }
    return 0;
}

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