Submission #677544

#	Time	Username	Problem	Language	Result	Execution time	Memory
677544		FedShat	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	652 ms	89524 KiB

long_mansion

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr ll INFLL = numeric_limits<ll>::max() / 2;

template<class T>
istream &operator>>(istream &is, vector<T> &a) {
    for (auto &i : a) {
        is >> i;
    }
    return is;
}

#ifdef __APPLE__
#include "../../debug.h"
#else
#define debug(...) 42
#endif

struct SegTree { // min, max, first >
    struct Node {
        int mn, mx;

        Node() {}
        Node(int x) {
            mn = x;
            mx = x;
        }
    };

    Node pull(const Node &a, const Node &b) {
        Node ans;
        ans.mn = min(a.mn, b.mn);
        ans.mx = max(a.mx, b.mx);
        return ans;
    }

    vector<Node> tree;
    int n;

    void build(int v, int l, int r, const vector<int> &a) {
        if (l + 1 == r) {
            tree[v] = a[l];
            return;
        }
        int m = (l + r) / 2;
        build(2 * v + 1, l, m, a);
        build(2 * v + 2, m, r, a);
        tree[v] = pull(tree[2 * v + 1], tree[2 * v + 2]);
    }

    SegTree(vector<int> a) {
        n = a.size();
        tree.resize(4 * n);
        build(0, 0, n, a);
    }

    int get_first_bol(int v, int l, int r, int li, int ri, int x) {
        if (li >= r || l >= ri || tree[v].mx <= x) {
            return n;
        }
        if (l + 1 == r) {
            return l;
        }
        int m = (l + r) / 2;
        int la = get_first_bol(2 * v + 1, l, m, li, ri, x);
        if (la != n) {
            return la;
        }
        return get_first_bol(2 * v + 2, m, r, li, ri, x);
    }

    int get_first_bol(int li, int ri, int x) {
        return get_first_bol(0, 0, n, li, ri, x);
    }

    int get_min(int v, int l, int r, int li, int ri) {
        if (li >= r || l >= ri) {
            return INF;
        }
        if (li <= l && r <= ri) {
            return tree[v].mn;
        }
        int m = (l + r) / 2;
        return min(get_min(2 * v + 1, l, m, li, ri), get_min(2 * v + 2, m, r, li, ri));
    }

    int get_min(int li, int ri) {
        return get_min(0, 0, n, li, ri);
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(0);
#ifdef __APPLE__
    freopen("input.txt", "r", stdin);
#endif
    int n;
    cin >> n;
    vector<int> c(n - 1);
    cin >> c;
    for (int &i : c) {
        --i;
    }
    vector<vector<int>> a(n);
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        a[i].resize(x);
        cin >> a[i];
        for (int &j : a[i]) {
            --j;
        }
    }
    int q;
    cin >> q;
    vector<array<int, 3>> lr, rl;
    for (int i = 0; i < q; ++i) {
        int l, r;
        cin >> l >> r;
        --l;
        --r;
        if (l <= r) {
            lr.push_back({l, r, i});
        } else {
            rl.push_back({n - l - 1, n - r - 1, i});
        }
    }
    vector<bool> ans(q, 1);
    auto solve = [&](vector<array<int, 3>> qq) {
        vector<vector<int>> ind(n);
        for (int i = 0; i < n; ++i) {
            for (int j : a[i]) {
                ind[j].push_back(i);
            }
        }
        vector<int> prv(n, -1), nxt(n, n); // prv[i] of c[i] and nxt[i] of c[i]
        for (int i = 0; i < n - 1; ++i) {
            const auto &v = ind[c[i]];
            auto it = upper_bound(v.begin(), v.end(), i) - v.begin();
            if (it != 0) {
                prv[i] = v[it - 1];
            }
        }
        for (int i = 0; i < n - 1; ++i) {
            const auto &v = ind[c[i]];
            auto it = upper_bound(v.begin(), v.end(), i) - v.begin();
            if (it != (int) v.size()) {
                nxt[i] = v[it];
            }
        }
        SegTree do1(nxt);
        vector<int> kek(n, n); // dlya kazdogo x first j na otr prv[x], chto nxt[j] > x
        for (int x = 0; x < n; ++x) {
            if (prv[x] == -1) {
                kek[x] = -1;
                continue;
            }
            kek[x] = do1.get_first_bol(prv[x], n, x);
            // for (int j = prv[x]; j < n; ++j) {
            //     if (nxt[j] > x) {
            //         kek[x] = j;
            //         break;
            //     }
            // }
        }
        SegTree do2(kek);
        for (auto [l, r, i] : qq) {
            debug(l + 1, r + 1, i);
            if (do2.get_min(l, r) < l) {
                ans[i] = 0;
            }
            // for (int x = l; x < r; ++x) {
            //     if (kek[x] < l) {
            //         ans[i] = 0;
            //         break;
            //     }
            // }
        }
    };
    solve(lr);
    reverse(c.begin(), c.end());
    reverse(a.begin(), a.end());
    solve(rl);
    for (auto i : ans) {
        if (i) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
}

Compilation message (stderr)

long_mansion.cpp: In lambda function:
long_mansion.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
long_mansion.cpp:171:13: note: in expansion of macro 'debug'
  171 |             debug(l + 1, r + 1, i);
      |             ^~~~~

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