Submission #1307014

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307014		Double_Slash	Long Mansion (JOI17_long_mansion)	C++20	100 / 100	1264 ms	113124 KiB

long_mansion

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

template <int(*f)(int, int), int I, int n = 500001>
struct St {
    int st[n << 1];

    void init() { fill(st, st + n * 2, I); }

    void upd(int i, int v) {
        for (st[i += n] = v; i >>= 1;) st[i] = f(st[i << 1], st[i << 1 | 1]);
    }

    int operator()(int l, int r) {
        int ret = I;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) ret = f(ret, st[l++]);
            if (r & 1) ret = f(ret, st[--r]);
        }
        return ret;
    }
};
St<[] (int a, int b) { return max(a, b); }, 0> mxst;
St<[] (int a, int b) { return min(a, b); }, 500000> mnst;

int main() {
    int n;
    cin >> n;
    int c[n];
    for (int i = 1; i < n; ++i) cin >> c[i];
    int last[n + 1]{}, hi[n + 1]{}, lo[n + 1]{};
    vector<int> a[n + 1], hip[n + 1], lop[n + 2];
    for (int i = 1; i <= n; ++i) {
        int b;
        cin >> b;
        a[i].resize(b);
        for (int &aij: a[i]) {
            cin >> aij;
            last[aij] = i;
        }
        i < n and (hi[i] = last[c[i]]);
        hip[hi[i]].emplace_back(i);
    }
    fill(last, last + n + 1, n + 1);
    fill(lo, lo + n + 1, n + 1);
    for (int i = n; i >= 1; --i) {
        for (int &aij: a[i]) last[aij] = i;
        i > 1 and (lo[i] = last[c[i - 1]]);
        lop[lo[i]].emplace_back(i);
    }
    mxst.init();
    set<int> s;
    for (int i = 0; i <= n; ++i) {
        auto it = s.upper_bound(-lo[i]);
        if (it != s.end() and -*it >= i) mxst.upd(i, -*it);
        for (int j: hip[i]) s.emplace(-j);
    }
    s.clear();
    mnst.init();
    for (int i = n + 1; i >= 1; --i) {
        auto it = s.upper_bound(hi[i]);
        if (it != s.end() and *it <= i) mnst.upd(i, *it);
        for (int j: lop[i]) s.emplace(j);
    }
    int q;
    for (cin >> q; q--;) {
        int x, y;
        cin >> x >> y;
        cout << ((y < x ? mxst(y + 1, x + 1) < x : mnst(x, y) > x) ? "YES\n" : "NO\n");
    }
}

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