Submission #197683

#	Time	Username	Problem	Language	Result	Execution time	Memory
197683		dennisstar	Long Mansion (JOI17_long_mansion)	C++17	10 / 100	3064 ms	31976 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], pos[500010];
vim l, r;
int Xk, Yk, lb;
 
inline bool Find(int L, int R, int X) {
	lb=lower_bound(all(pos[X]), L)-pos[X].begin();
	return (lb<pos[X].size()&&pos[X][lb]<=R);
}
 
int main() {
	scanf("%d", &N);
	C.resize(N); B.resize(N+1); l.resize(N+1); r.resize(N+1);
	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);
		for (auto &j:A[i]) pos[j].eb(i);
	}
	for (int i=1; i<=N; i++) {
		l[i]=r[i]=i;
		for (int fl; ; ) {
			fl=0;
			while (l[i]>1 && Find(l[i], r[i], C[l[i]-1])) {
				r[i]=max(r[i], r[l[i]-1]);
				l[i]=l[l[i]-1];
				fl=1;
			}
			while (r[i]<N && Find(l[i], r[i], C[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 'bool Find(int, int, int)':
long_mansion.cpp:25:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  return (lb<pos[X].size()&&pos[X][lb]<=R);
          ~~^~~~~~~~~~~~~~
long_mansion.cpp: In function 'int main()':
long_mansion.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
long_mansion.cpp:31: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:33: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:35: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:51:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
long_mansion.cpp:53: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: 0 / 15
• Subtask 4: 0 / 75