제출 #1162595

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1162595		jerzyk	Long Mansion (JOI17_long_mansion)	C++20	100 / 100	213 ms	81084 KiB

long_mansion

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1000'000'007LL;
const int N = 1<<19;
int l[N], r[N], lst[N], ned[N];
int mi[N][20];
vector<int> key[N];
pair<int, int> ran[N];

int Query(int a, int b)
{
    int d = b - a + 1;
    int p = 31 - __builtin_clz(d);
    return min(mi[a][p], mi[b - (1<<p) + 1][p]);
}

int BS(int a, int b, int n)
{
    int p = b, k = n, s;
    while(p < k)
    {
        s = (p + k + 1) / 2;
        if(Query(b + 1, s) < a)
            k = s - 1;
        else
            p = s;
    }
    return p;
}

void Solve()
{
    int n, m, q;
    cin >> n;
    r[0] = n + 10; l[n + 1] = -1;
    for(int i = 1; i < n; ++i)
        cin >> ned[i];
    for(int i = 1; i <= n; ++i)
    {
        int x;
        l[i] = lst[ned[i - 1]];
        mi[i][0] = l[i];
        cin >> m;
        for(int j = 1; j <= m; ++j)
        {
            cin >> x; lst[x] = i;
            key[i].pb(x);
        }
    }
    for(int i = n; i >= 1; --i)
        for(int j = 1; i + (1<<j) - 1 <= n; ++j)
            mi[i][j] = min(mi[i][j - 1], mi[i + (1<<(j - 1))][j - 1]);
    for(int i = 0; i <= n; ++i) lst[i] = n + 1;
    for(int i = n; i >= 1; --i)
    {
        r[i] = lst[ned[i]];
        for(int j = 0; j < (int)key[i].size(); ++j)
            lst[key[i][j]] = i;
    }
    for(int i = 1; i <= n; ++i)
    {
        int a = i, b = i;
        //cout << "S: " << i << "\n";
        while(true)
        {
            while(b >= r[a - 1])
            {
                b = max(b, ran[a - 1].nd);
                a = ran[a - 1].st;
            }
            int nb = BS(a, b, n);
            //cout << a << " " << b << "\n";
            if(nb == b) break;
            b = nb;
        }
        //cout << "\n";
        ran[i] = make_pair(a, b);
    }
    cin >> q;
    for(int i = 1; i <= q; ++i)
    {
        int a, b;
        cin >> a >> b;
        if(ran[a].st <= b && ran[a].nd >= b)
            cout << "YES\n";
        else
            cout << "NO\n";
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //int t; cin >> t;
    //while(t--)
        Solve();

    return 0;
}

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