Submission #1210037

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210037		mychecksedad	Long Mansion (JOI17_long_mansion)	C++20	0 / 100	141 ms	28560 KiB

long_mansion

/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 5e5+100, M = 1e5+10, K = 21, MX = 30;

mt19937 rng(342236234);

int rn(int l, int r){
  return uniform_int_distribution<int>(l,r)(rng);
}

int n, c[N], used[N], ptr, T[4*N][2];
vector<int> A[N];
array<int, 2> a[N];

void build(int sz){
  for(int i = 0; i <= 4*sz; ++i) T[i][0] = 1, T[i][1] = n;
}
void upd(int l, int r, int ql, int qr, int k, int val){
  if(ql > r || l > qr) return;
  if(ql <= l && r <= qr){
    T[k][1] = min(T[k][1], val);
    return;
  }
  int mid = l+r>>1;
  upd(l, mid, ql, qr, k<<1, val);
  upd(mid+1, r, ql, qr, k<<1|1, val);
}

void upd2(int l, int r, int ql, int qr, int k, int val){
  if(ql > r || l > qr) return;
  if(ql <= l && r <= qr){
    T[k][0] = max(T[k][0], val);
    return;
  }
  int mid = l+r>>1;
  upd2(l, mid, ql, qr, k<<1, val);
  upd2(mid+1, r, ql, qr, k<<1|1, val);
}
array<int, 2> get(int l, int r, int p, int k){
  if(l == r){
    return array<int, 2>{T[k][0], T[k][1]};
  }
  int mid = l+r>>1;
  array<int, 2> v;
  if(p <= mid){
    v = get(l, mid, p, k<<1);
  }else{
    v = get(mid+1, r, p, k<<1|1);
  }
  v[0] = max(v[0], T[k][0]);
  v[1] = min(v[1], T[k][1]);
  return v;
}

void apply(int l, int r){
  upd(1, n, l, r, 1, r);
}
void apply2(int l, int r){
  upd2(1, n, l, r, 1, l);
}
void solve(){
  cin >> n;
  for(int i = 1; i < n; ++i){
    cin >> c[i];
  }
  for(int i = 1; i <= n; ++i){
    a[i][0] = 1, a[i][1] = n;
    int x; cin >> x;
    A[i].resize(x);  
    for(int &y: A[i]) cin >> y;
  }

  build(n);

  set<pii> S;
  S.insert({0, -1});
  vector<int> last_key(n + 1, -1);
  c[n] = 0;
  vector<vi> s_door(n + 1);
  for(int i = 1; i < n; ++i){  
    for(int x: A[i]){
      for(auto p: s_door[x]){
        S.erase(pii{p, x});
      }
      s_door[x].clear();
      last_key[x] = i;
    }
    auto it = S.upper_bound(pii{last_key[c[i]] - 1, MOD});
    if(it != S.end()){
      apply((*it).ff + 1, i);
    }
    s_door[c[i]].pb(i);
    S.insert({i, c[i]});
  }

  S.clear();
  S.insert({n, -1});
  c[n] = 0;
  fill(all(last_key), n + 2);
  for(int i = 0; i <= n; ++i){
    s_door[i].clear();
  }
  for(int i = n; i > 1; --i){  
    for(int x: A[i]){
      for(auto p: s_door[x]){
        S.erase(pii{p, x});
      }
      s_door[x].clear();
      last_key[x] = i;
    }
    auto it = S.upper_bound(pii{last_key[c[i - 1]], -2});
    if(it != S.begin()){
      --it;
      apply2(i, (*it).ff);
    }
    s_door[c[i-1]].pb(i);
    S.insert({i-1, c[i-1]});
  }

  for(int i = 1; i <= n; ++i){
    a[i] = get(1, n, i, 1);
  }


  // for(int i = 1; i <= n; ++i){
  //   cerr << a[i][0] << ' ' << a[i][1] << '\n';
  // }

  
  int q; cin >> q;
  for(int i = 1; i <= q; ++i){
    int x, y; cin >> x >> y;
    if(a[x][0] <= y && a[x][1] >= y){
      cout << "YES\n";
    }else{
      cout << "NO\n";
    }
  }
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  while(tt--){
    solve();
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
} 

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