제출 #990326

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
990326		xyzaa	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	610 ms	50256 KiB

long_mansion

#include <bits/stdc++.h>
using namespace std;

const int N = 500008;
int n, q, c[N], sz[N], L[N], R[N], cl[N], cr[N];
bool proc[N];
vector<int> key[N];

void dnc(int l, int r) {
    if (l > r) return;
    int mid = (l + r) / 2;
    if (proc[mid]) return;
    while (true) {
        if (L[mid] != 1 && cr[L[mid] - 1] <= R[mid]) {
            L[mid]--;
            if (proc[L[mid]]) {
                L[mid] = min(L[L[mid]], L[mid]);
                R[mid] = max(R[L[mid]], R[mid]);
            }
        } else if (R[mid] != n && cl[R[mid]] >= L[mid]) {
            R[mid]++;
            if (proc[R[mid]]) {
                L[mid] = min(L[R[mid]], L[mid]);
                R[mid] = max(R[R[mid]], R[mid]);
            }
        } else break;
    }
    proc[mid] = true;
    dnc(l, mid);
    dnc(mid + 1, r);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int i = 1; i < n; i++) cin >> c[i];
    for (int i = 1; i <= n; i++) {
        cin >> sz[i];
        L[i] = R[i] = i;
        for (int j = 0, x; j < sz[i]; j++) {
            cin >> x;
            key[x].push_back(i);
        }
    }
    for (int i = 1; i <= n - 1; i++) {
        auto it = upper_bound(key[c[i]].begin(), key[c[i]].end(), i);
        if (it == key[c[i]].begin()) cl[i] = -1;
        else cl[i] = *(--it);
        it = lower_bound(key[c[i]].begin(), key[c[i]].end(), i + 1);
        if (it == key[c[i]].end()) cr[i] = n + 1;
        else cr[i] = *it;
    }
    dnc(1, n);
    // for (int i = 1; i <= n; i++) cout << L[i] << ' ' << R[i] << '\n';
    cin >> q;
    while (q--) {
        int x, y;
        cin >> x >> y;
        if (L[x] <= y && y <= R[x]) cout << "YES\n";
        else cout << "NO\n";
    }
}

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