Submission #24102

#	Time	Username	Problem	Language	Result	Execution time	Memory
24102		jiaqiyang	Long Mansion (JOI17_long_mansion)	C++14	100 / 100	276 ms	40184 KiB

long_mansion

#include <cctype>
#include <cstdio>
#include <cstring>
#include <vector>

const int N = 500000 + 10;

int nextInt() {
  char ch;
  while (!isdigit(ch = getchar())) {}
  int res = ch - '0';
  while (isdigit(ch = getchar())) res = 10 * res + ch - '0';
  return res;
}

int n, c[N], left[N], right[N];

std::vector<int> a[N];

int pred[N], succ[N];

void init() {
  static int last[N];
  memset(last, 0, sizeof last);
  for (int i = 1; i < n; ++i) {
    for (int j = 0; j < a[i].size(); ++j) last[a[i][j]] = i;
    pred[i] = last[c[i]];
  }
  memset(last, 0, sizeof last);
  for (int i = n; i > 1; --i) {
    for (int j = 0; j < a[i].size(); ++j) last[a[i][j]] = i;
    succ[i - 1] = last[c[i - 1]];
  }
}

inline bool check(int l, int r, int x) {
  return (pred[x] && l <= pred[x] && pred[x] <= r) || (succ[x] && l <= succ[x] && succ[x] <= r);
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i < n; ++i) c[i] = nextInt();
  for (int i = 1; i <= n; ++i)
    for (int b = nextInt(); b--;)
      a[i].push_back(nextInt());
  init();
  for (int i = 1; i <= n; ++i) {
    int &l = left[i] = i, &r = right[i] = i;
    while (1) {
      if (l > 1 && check(l, r, l - 1)) {
        r = std::max(r, right[l - 1]);
        l = left[l - 1];
        continue;
      }
      if (r < n && check(l, r, r)) {
        ++r;
        continue;
      }
      break;
    }
  }
  for (int q = nextInt(); q--;) {
    int x = nextInt(), y = nextInt();
    puts(left[x] <= y && y <= right[x] ? "YES" : "NO");
  }
  return 0;
}

Compilation message (stderr)

long_mansion.cpp: In function 'void init()':
long_mansion.cpp:26:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < a[i].size(); ++j) last[a[i][j]] = i;
                       ^
long_mansion.cpp:31:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < a[i].size(); ++j) last[a[i][j]] = i;
                       ^
long_mansion.cpp: In function 'int main()':
long_mansion.cpp:41:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
                  ^

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