Submission #991239

#	Time	Username	Problem	Language	Result	Execution time	Memory
991239		_callmelucian	Long Mansion (JOI17_long_mansion)	C++14	100 / 100	598 ms	117700 KiB

long_mansion

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

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

const int mn = 5e5 + 5;
int spt[mn][19], req[mn], last[mn], reachLeft[mn], reachRight[mn], ans[mn];
vector<int> key[mn], violate[mn];

int spQry (int l, int r) {
    int p = 31 - __builtin_clz(r - l + 1);
    return max(spt[l][p], spt[r - (1 << p) + 1][p]);
}

struct query {
    int x, y, id;

    query() : x(0), y(0), id(0) {}
    query (int a, int b, int c) : x(a), y(b), id(c) {}

    bool operator < (const query &o) const {
        return x < o.x;
    }

    bool type() { return x < y; }

    query rever (int n) {
        return query(n - x + 1, n - y + 1, id);
    }
};

void solve (int n, vector<query> &qry) {
    // calculate reachLeft
    for (int i = 1; i <= n; i++) last[i] = 0;
    for (int i = 1; i <= n; i++) {
        reachLeft[i] = last[req[i]];
        for (int u : key[i]) last[u] = i;
    }
    reachLeft[n + 1] = INT_MIN;

    // calculate reachRight
    for (int i = 1; i <= n; i++) last[i] = n + 1;
    for (int i = n; i >= 1; i--) {
        reachRight[i] = last[req[i + 1]];
        for (int u : key[i]) last[u] = i;
    }
    reachRight[0] = INT_MAX;

    // build sparse table
    for (int i = 0; i <= n; i++) spt[i][0] = reachRight[i];
    for (int s = 1; (1 << s) <= n + 1; s++) {
        for (int i = 0; i + (1 << s) - 1 <= n; i++) {
            int p = s - 1;
            spt[i][s] = max(spt[i][p], spt[i + (1 << p)][p]);
        }
    }

    for (int i = 1; i <= n; i++) violate[i].clear();
    for (int i = 2; i <= n; i++) {
        int k = reachLeft[i];
        for (int step = n; step >= 1; step /= 2) {
            while (k + step < i && spQry(reachLeft[i], k + step - 1) < i) k += step;
        }
        //cout << "pos " << i << " first to violate " << k + 1 << "\n";
        violate[k + 1].push_back(i);
    }

    int pos = -1;
    priority_queue<int> pq;
    for (query cur : qry) {
        while (pos < cur.x) {
            pos++;
            for (int u : violate[pos]) pq.push(-u);
        }
        while (pq.size() && -pq.top() <= cur.x) pq.pop();
        int bound = (pq.size() ? -pq.top() : INT_MAX);
        //cout << "prep query " << cur.id << " " << bound << "\n";
        ans[cur.id] = (cur.y < bound ? 1 : 0);
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n; cin >> n;
    for (int i = 2; i <= n; i++) cin >> req[i];
    for (int i = 1; i <= n; i++) {
        int k; cin >> k;
        key[i] = vector<int>(k);
        for (int j = 0; j < k; j++) cin >> key[i][j];
    }

    int q; cin >> q;
    vector<query> ltr, rtl;

    for (int i = 0; i < q; i++) {
        int x, y; cin >> x >> y;
        query cur(x, y, i);
        if (cur.type()) ltr.push_back(cur);
        else rtl.push_back(cur.rever(n));
    }
    sort(all(ltr)); sort(all(rtl));

    solve(n, ltr);

    reverse(req + 1, req + 1 + n);
    reverse(key + 1, key + 1 + n);
    for (int i = n; i >= 1; i--)
        req[i] = req[i - 1];

    solve(n, rtl);

    for (int i = 0; i < q; i++)
        cout << (ans[i] ? "YES" : "NO") << "\n";

    return 0;
}

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