Submission #529261

#	Time	Username	Problem	Language	Result	Execution time	Memory
529261		Radman_	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	1174 ms	75928 KiB

long_mansion

//                  //
//     Radmanシ     //
//                 //
#include <bits/stdc++.h>

using namespace std;

#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")

#define int long long
//typedef long long ll;

typedef pair<int, int> pii;
typedef pair<int, pii> pip;
typedef pair<pii, int> ppi;
typedef pair<pii, pii> ppp;
#define F first
#define S second

#define _ios_ ios::sync_with_stdio(false); cin.tie(0),cout.tie(0);

#define debug(x) cerr << #x << " = " << x << endl
#define debug2(x,y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl

void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H) ;
  debug_out(T...);
}
#define debugn(...)  cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)

#define all(x) x.begin(), x.end()

const int MAXN = 5e5+5, MAXSQ = 550, INF = 1e9;
int c[MAXN], mark[MAXN], key[MAXN];
pii ans[MAXN], suf[MAXN], pre[MAXN];
vector<int> a[MAXN], v;
int n;

inline void f(int l, int r, int mid)
{
    for (int i = l; i <= mid; i++)
    {
        suf[i] = {i, mid};
        mark[i] = 0;
    }
    for (int i: v)
        key[i] = 0;
    v.clear();
    int p = mid;
    for (int i = mid; i >= l; i--)
    {
        for (int j: a[i])
        {
            key[j] = 1;
            v.push_back(j);
        }
        while (p < r && key[c[p]])
        {
            p++;
            for (int j: a[p])
            {
                key[j] = 1;
                v.push_back(j);
            }
        }
        suf[i].S = p;
        if (i > l && key[c[i-1]])
            mark[i] = 1;
    }
    for (int i = l+1; i <= mid; i++)
    {
        if (mark[i])
            suf[i] = suf[i-1];
    }
    for (int i = l; i <= mid; i++)
    {
        if (ans[i].S == mid)
            ans[i] = suf[ans[i].F];
    }


    for (int i = mid+1; i <= r; i++)
    {
        pre[i] = {mid+1, i};
        mark[i] = 0;
    }
    for (int i: v)
        key[i] = 0;
    v.clear();
    p = mid+1;
    for (int i = mid+1; i <= r; i++)
    {
        for (int j: a[i])
        {
            key[j] = 1;
            v.push_back(j);
        }
        while (p > l && key[c[p-1]])
        {
            p--;
            for (int j: a[p])
            {
                key[j] = 1;
                v.push_back(j);
            }
        }
        pre[i].F = p;
        if (i < r && key[c[i]])
            mark[i] = 1;
    }
    for (int i = r-1; i > mid; i--)
    {
        if (mark[i])
            pre[i] = pre[i+1];
    }
    for (int i = mid+1; i <= r; i++)
    {
        if (ans[i].F == mid+1)
            ans[i] = pre[ans[i].S];
    }
    return;
}

void solve(int l, int r)
{
    //debug2(l, r);
    if (l == r)
    {
        ans[l] = {l, r};
        return;
    }
    int mid = (r + l) >> 1;
    solve(l, mid);
    solve(mid+1, r);
    f(l, r, mid);
    return;
}

int32_t main()
{
    _ios_
    int n;
    cin >> n;
    for (int i = 1; i < n; i++)
        cin >> c[i];
    for (int i = 1; i <= n; i++)
    {
        int k;
        cin >> k;
        for (int j = 1; j <= k; j++)
        {
            int x;
            cin >> x;
            a[i].push_back(x);
        }
    }
    solve(1, n);
    int q;
    cin >> q;
    for (int i = 1; i <= q; i++)
    {
        int x, y;
        cin >> x >> y;
        if (ans[x].F <= y && y <= ans[x].S)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}

/*
5
1 2 3 4
2 2 3
1 1
1 1
1 3
1 4
4
2 4
4 2
1 5
5 3

*/

Compilation message (stderr)

long_mansion.cpp:9: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    9 | #pragma GCC optimization("O3")
      | 
long_mansion.cpp:10: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   10 | #pragma GCC optimization("unroll-loops")
      |

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