Submission #204913

#	Time	Username	Problem	Language	Result	Execution time	Memory
204913		extraterrestrial	Long Mansion (JOI17_long_mansion)	C++14	10 / 100	3049 ms	26356 KiB

long_mansion

#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
//#define int ll

const int N = 5e5 + 10;
const int INF = 1e9 + 10;
int need_l[N], need_r[N];
int get_max_r(int l, int r) {
  int res = 0;
  for (int i = l; i <= r; i++) {
    res = max(res, need_r[i]);
  }
  return res;
}

int get_min_l(int l, int r) {
  int res = INF;
  for (int i = l; i <= r; i++) {
    res = min(res, need_l[i]);
  }
  return res;
}

int c[N], mx[N], mn[N];
vector<int> have[N];

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n;
  cin >> n;
  for (int i = 1; i < n; i++) {
    cin >> c[i];
  }
	for (int i = 1; i <= n; i++) {
    int cnt;
    cin >> cnt;
    have[i].resize(cnt);
    for (auto &it : have[i]) {
      cin >> it;
    }
  }
  map<int, int> prv;
  for (int i = 1; i < n; i++) {
    for (auto it : have[i]) {
      prv[it] = i;
    }  
    need_l[i] = prv[c[i]];
  }
  prv = {};
  for (int i = n; i > 1; i--) {
    for (auto it : have[i]) {
      prv[it] = i;
    }
    need_r[i] = prv[c[i - 1]];
    if (need_r[i] == 0) {
      need_r[i] = n + 1;
    }
  }
  for (int i = 1; i < n; i++) {
    if (need_l[i] == 0) {
      mx[i] = 0;
      continue;
    }
    int l = need_l[i], r = i + 1;
    while (r - l > 1) {
      int mid = (l + r) / 2;
      if (get_max_r(need_l[i] + 1, mid) > i) {
        r = mid;
      }
      else {
        l = mid;
      }
    }
    mx[i] = l;
  }
  for (int i = 2; i <= n; i++) {
    if (need_r[i] == 0) {
      mn[i] = n + 1;
      continue;
    }
    int l = i - 1, r = need_r[i];
    while (r - l > 1) {
      int mid = (l + r) / 2;
      if (get_min_l(mid, need_r[i] - 1) < i) {
        l = mid;
      }
      else {
        r = mid;
      }
    }
    mn[i] = r;
  } 
  int q;
  cin >> q;
  for (int i = 0; i < q; i++) {
    int l, r;
    cin >> l >> r;
    if (l == r) {
      cout << "YES\n";
      continue;
    }
    if (l < r) {
      bool ok = true;
      for (int j = l; j < r; j++) {
        if (l > mx[j]) {
          ok = false;
          break;
        }
      }
      cout << (ok ? "YES\n" : "NO\n");
    }
    else {
      bool ok = true;
      for (int j = l; j > r; j--) {
        if (l < mn[j]) {
          ok = false;
          break;
        }
      }
      cout << (ok ? "YES\n" : "NO\n");
    }
  }
} 

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