Submission #197682

#	Time	Username	Problem	Language	Result	Execution time	Memory
197682		dennisstar	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	448 ms	54436 KiB

long_mansion

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define fi first
#define se second
#define ryan bear
#define sq(X) ((X)*(X))
#define eb emplace_back
#define all(V) (V).begin(), (V).end()
#define unq(V) (V).erase(unique(all(V)), (V).end())
using namespace std;
typedef long long ll;
typedef vector<ll> vlm;
typedef vector<int> vim;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

int N, Q;
vim C, B, A[500010];
vim l, r, pr, nx, im;
int Xk, Yk, lb;

inline bool Find(int L, int R, int X) {
	return ((pr[X]&&L<=pr[X]&&pr[X]<=R) || (nx[X]&&L<=nx[X]&&nx[X]<=R));
}

void init() {
	C.resize(N); B.resize(N+1);
	l.resize(N+1); r.resize(N+1);
	pr.resize(N+1); nx.resize(N+1);
	im.resize(N+1);
}

int main() {
	scanf("%d", &N);
	init();
	for (int i=1; i<N; i++) scanf("%d", &C[i]);
	for (int i=1; i<=N; i++) {
		scanf("%d", &B[i]);
		A[i].resize(B[i]);
		for (auto &j:A[i]) scanf("%d", &j);
	}

	fill(all(im), 0);
	for (int i=1; i<N; i++) {
		for (auto &j:A[i]) im[j]=i;
		pr[i]=im[C[i]];
	}
	fill(all(im), 0);
	for (int i=N; i>1; i--) {
		for (auto &j:A[i]) im[j]=i;
		nx[i-1]=im[C[i-1]];
	}

	for (int i=1; i<=N; i++) {
		l[i]=r[i]=i;
		for (int fl; ; ) {
			fl=0;
			if (l[i]>1 && Find(l[i], r[i], l[i]-1)) {
				r[i]=max(r[i], r[l[i]-1]);
				l[i]=l[l[i]-1];
				fl=1;
			}
			else if (r[i]<N && Find(l[i], r[i], r[i])) { r[i]++; fl=1; }
			if (!fl) break;
		}
	}

	scanf("%d", &Q);
	while (Q--) {
		scanf("%d %d", &Xk, &Yk);
		if (l[Xk]<=Yk&&Yk<=r[Xk]) puts("YES");
		else puts("NO");
	}
	return 0;
}

Compilation message (stderr)

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:35:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
long_mansion.cpp:37:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i=1; i<N; i++) scanf("%d", &C[i]);
                          ~~~~~^~~~~~~~~~~~~
long_mansion.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &B[i]);
   ~~~~~^~~~~~~~~~~~~
long_mansion.cpp:41:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for (auto &j:A[i]) scanf("%d", &j);
                      ~~~~~^~~~~~~~~~
long_mansion.cpp:69:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
long_mansion.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &Xk, &Yk);
   ~~~~~^~~~~~~~~~~~~~~~~~~

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