Submission #1135573

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135573		Hamed_Ghaffari	Long Mansion (JOI17_long_mansion)	C++20	100 / 100	838 ms	116176 KiB

long_mansion

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,sse4,sse4.2,lzcnt,popcnt")

#define pb push_back

const int MXN = 5e5+5;

int n, q, C[MXN], L[MXN], R[MXN], dpl[MXN], dpr[MXN], lst[MXN];
vector<int> A[MXN], ins[MXN], del[MXN], rem[MXN];
set<int> st;

int32_t main() {
  cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
  cin >> n;
  for(int i=1; i<n; i++) cin >> C[i];
  for(int i=1, b; i<=n; i++) {
    cin >> b;
    A[i] = vector<int>(b);
    for(int &j : A[i]) cin >> j;
  }
  memset(lst, -1, sizeof(lst));
  for(int i=1; i<n; i++) {
    for(int x : A[i]) lst[x] = i;
    L[i] = lst[C[i]];
  }
  memset(lst, -1, sizeof(lst));
  for(int i=n; i>=2; i--) {
    for(int x : A[i]) lst[x] = i;
    R[i] = lst[C[i-1]];
  }
  ins[1].pb(1);
  for(int i=n; i>=2; i--) {
    if(i==n || L[i]!=i) st.insert(i);
    for(int x : rem[i]) st.erase(x);
    if(L[i]!=-1) rem[L[i]].pb(i);
    if(R[i]!=-1 && (st.empty() || (*st.begin())>=R[i])) continue;
    ins[i].pb(i);
    if(R[i]!=-1) del[(*prev(st.lower_bound(R[i])))+1].pb(i);
  }
  st.clear();
  for(int i=1; i<=n; i++) {
    for(int x : ins[i]) st.insert(x);
    for(int x : del[i]) st.erase(x);
    ins[i].clear();
    del[i].clear();
    rem[i].clear();
    dpl[i] = *st.rbegin();
  }
  st.clear();
  ins[n].pb(n);
  for(int i=1; i<n; i++) {
    if(i==1 || R[i]!=i) st.insert(i);
    for(int x : rem[i]) st.erase(x);
    if(R[i]!=-1) rem[R[i]].pb(i);
    if(L[i]!=-1 && (st.empty() || (*st.rbegin())<=L[i])) continue;
    ins[i].pb(i);
    if(L[i]!=-1) del[(*st.upper_bound(L[i]))-1].pb(i);
  }
  st.clear();
  for(int i=n; i>=1; i--) {
    for(int x : ins[i]) st.insert(x);
    for(int x : del[i]) st.erase(x);
    dpr[i] = *st.begin();
  } 
  cin >> q;
  while(q--) {
    int x, y;
    cin >> x >> y;
    cout << (dpl[x]<=y && y<=dpr[x] ? "YES" : "NO") << '\n';
  }
  return 0;
}

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