Submission #1159125

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159125		OI_Account	Long Mansion (JOI17_long_mansion)	C++20	100 / 100	533 ms	98056 KiB

long_mansion

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

const int N = 500'000;
const int M = 19;

int n, c[N + 10];
int last[N + 10], lft[N + 10], rght[N + 10];
int mn[N + 10][M + 2], ansL[N + 10], ansR[N + 10];
int segL[4 * N + 10], segR[4 * N + 10];
vector<int> vec[N + 10];

void readInput() {
    cin >> n;
    for (int i = 1; i < n; i++)
        cin >> c[i];
    for (int i = 1; i <= n; i++) {
        int b;
        cin >> b;
        while (b--) {
            int x;
            cin >> x;
            vec[i].push_back(x);
        }
    }
}

void calcLft() {
    fill(last + 1, last + n + 1, 0);
    for (int i = 1; i < n; i++) {
        for (auto x: vec[i])
            last[x] = i;
        lft[i] = last[c[i]];
    }
}

void calcRght() {
    fill(last + 1, last + n + 1, n + 1);
    for (int i = n; i >= 2; i--) {
        for (auto x: vec[i])
            last[x] = i;
        rght[i - 1] = last[c[i - 1]] - 1;
        //cout << "rght " << i - 1 << ": " << rght[i - 1] << '\n';
    }
}




void update(int st, int en, int x, int y, int id = 1, int l = 1, int r = n + 1) {
    if (en <= l || r <= st)
        return;
    if (st <= l && r <= en) {
        segL[id] = max(segL[id], x);
        segR[id] = min(segR[id], y);
        return;
    }
    int mid = (l + r) >> 1;
    update(st, en, x, y, id << 1, l, mid);
    update(st, en, x, y, id << 1 | 1, mid, r);
}

void build() {
    for (int i = 1; i <= 4 * n + 5; i++) {
        segL[i] = 1;
        segR[i] = n;
    }
}

void calcAns(pair<int, int> p = {1, n}, int id = 1, int l = 1, int r = n + 1) {
    p.first = max(p.first, segL[id]);
    p.second = min(p.second, segR[id]);
    if (l + 1 == r) {
        ansL[l] = p.first;
        ansR[l] = p.second;
        return;
    }
    int mid = (l + r) >> 1;
    calcAns(p, id << 1, l, mid);
    calcAns(p, id << 1 | 1, mid, r);
}

void addSeg(int l, int r) {
    //cout << "Seg " << l << ' ' << r << '\n';
    update(l, r + 1, l, r);
}

void calcRmqL() {
    for (int i = 1; i < n; i++)
        mn[i][0] = lft[i];
    for (int j = 1; j <= M; j++)
        for (int i = 1; i + (1 << j) - 1 < n; i++)
            mn[i][j] = min(mn[i][j - 1], mn[i + (1 << (j - 1))][j - 1]);
}

int getMinL(int l, int r) {
    int lg = 31 - __builtin_clz(r - l + 1);
    return min(mn[l][lg], mn[r - (1 << lg) + 1][lg]);
}

void solveL() {
    calcRmqL();
    for (int i = 1; i < n; i++) {
        if (rght[i] == n)
            update(i + 1, n + 1, i + 1, n);
        else {
            int l = i, r = rght[i] + 1;
            while (r - l > 1) {
                int mid = (l + r) >> 1;
                if (getMinL(mid, rght[i]) <= i)
                    l = mid;
                else
                    r = mid;
            }
            if (l != i)
                update(i + 1, l + 1, i + 1, n);
        }
    }
}

void calcRmqR() {
    for (int i = 1; i < n; i++)
        mn[i][0] = rght[i];
    for (int j = 1; j <= M; j++)
        for (int i = 1; i + (1 << j) - 1 < n; i++)
            mn[i][j] = max(mn[i][j - 1], mn[i + (1 << (j - 1))][j - 1]);
}

int getMaxR(int l, int r) {
    int lg = 31 - __builtin_clz(r - l + 1);
    return max(mn[l][lg], mn[r - (1 << lg) + 1][lg]);
}

void solveR() {
    calcRmqR();
    for (int i = 1; i < n; i++) {
        if (lft[i] == 0)
            update(1, i + 1, 1, i);
        else {
            int l = lft[i] - 1, r = i;
            while (r - l > 1) {
                int mid = (l + r) >> 1;
                if (getMaxR(lft[i], mid) >= i)
                    r = mid;
                else
                    l = mid;
            }
            if (r != i)
                update(r + 1, i + 1, 1, i);
        }
    }
}

void query() {
    int x, y;
    cin >> x >> y;
    cout << (ansL[x] <= y && y <= ansR[x]? "YES": "NO") << '\n';
}

void answerQuery() {
    int q;
    cin >> q;
    while (q--)
        query();
    cout.flush();
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    readInput();
    calcLft();
    calcRght();
    build();
    solveL();
    solveR();
    calcAns();
    answerQuery();
    return 0;
}

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