Submission #1037541

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037541		juicy	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	181 ms	82100 KiB

long_mansion

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 5e5 + 5, LG = 19;

int n, q;
int c[N], lt[N], rt[N], lst[N], mi[N], ma[N], spt[LG][N], lg[N];
vector<int> key[N];

void expand(int i) {
  for (int j = LG - 1; ~j; --j) {
    if (ma[i] + (1 << j) <= n && spt[j][ma[i]] >= mi[i]) {
      ma[i] += 1 << j;
    }
  }
}

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

  cin >> n;
  for (int i = 1; i < n; ++i) {
    cin >> c[i];
  }  
  for (int i = 1; i <= n; ++i) {
    int b; cin >> b;
    key[i].resize(b);
    for (int &x : key[i]) {
      cin >> x;
      lst[x] = i;
    }
    lt[i] = lst[c[i]];
  }
  fill(lst, lst + n + 1, n + 1);
  for (int i = n; i > 0; --i) {
    rt[i] = lst[c[i]];
    for (int x : key[i]) {
      lst[x] = i;
    }
  }
  for (int i = 2; i <= n; ++i) {
    lg[i] = lg[i / 2] + 1;
  }
  for (int i = 1; i <= n; ++i) {
    spt[0][i] = lt[i];
  }
  for (int j = 1; j <= lg[n]; ++j) {
    for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
      spt[j][i] = min(spt[j - 1][i], spt[j - 1][i + (1 << j - 1)]);
    } 
  }
  vector<int> st;
  for (int i = 1; i <= n; ++i) {
    mi[i] = ma[i] = i;
    expand(i);
    while (st.size() && rt[st.back()] <= ma[i]) {
      mi[i] = min(mi[i], mi[st.back()]);
      ma[i] = max(ma[i], ma[st.back()]);
      expand(i);
      st.pop_back();
    }
    st.push_back(i);
  }
  cin >> q;
  while (q--) {
    int x, y; cin >> x >> y;
    cout << (mi[x] <= y && y <= ma[x] ? "YES" : "NO") << "\n";
  }
  return 0;
}

Compilation message (stderr)

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:56:61: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   56 |       spt[j][i] = min(spt[j - 1][i], spt[j - 1][i + (1 << j - 1)]);
      |                                                           ~~^~~

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