Submission #62985

#	Time	Username	Problem	Language	Result	Execution time	Memory
62985		kingpig9	Long Mansion (JOI17_long_mansion)	C++11	25 / 100	2113 ms	158232 KiB

long_mansion

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e5 + 10;

//#define debug(...) fprintf(stderr, __VA_ARGS__)
#define debug(...)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

int N, Q;
int C[MAXN];
int L[MAXN], R[MAXN];
vector<int> A[MAXN];
bool has[MAXN];

void small() {
	for (int i = 1; i <= N; i++) {
		L[i] = R[i] = i;
		for (int j = 1; j <= N; j++) {
			has[j] = false;
		}
		for (int x : A[i]) {
			has[x] = true;
		}

		//ok let's go!
		while (true) {
			//extend left
			if (L[i] > 1) {
				int c = C[L[i] - 1];
				if (has[c]) {
					L[i]--;
					for (int x : A[L[i]]) {
						has[x] = true;
					}
					continue;
				}
			}

			//extend right
			if (R[i] < N) {
				int c = C[R[i]];
				if (has[c]) {
					R[i]++;
					for (int x : A[R[i]]) {
						has[x] = true;
					}
					continue;
				}
			}
			break;
		}
	}
}

vector<int> indk[21], indc[21];

void large() {
	for (int i = 1; i <= N; i++) {
		for (int x : A[i]) {
			indk[x].push_back(i);
		}
	}
	for (int i = 1; i < N; i++) {
		indc[C[i]].push_back(i);
	}

	for (int i = 1; i <= N; i++) {
		debug("----------------------------------i = %d----------------------------------\n", i);
		L[i] = R[i] = i;
		for (int j = 1; j <= 20; j++) {
			has[j] = false;
		}
		for (int x : A[i]) {
			has[x] = true;
		}

		while (true) {
			debug("----------L[%d] = %d, R[%d] = %d--------\n", i, L[i], i, R[i]);
			//extend left, update colors which it has
			vector<int> vhas, vnohas;
			for (int j = 1; j <= 20; j++) {
				if (has[j]) {
					debug("has %d\n", j);
					vhas.push_back(j);
				} else {
					vnohas.push_back(j);
				}
			}

			int lbarrier = 0, rbarrier = N;
			for (int c : vnohas) {
				//whatever is < i
				auto it = lower_bound(all(indc[c]), i);
				if (it != indc[c].end()) {
					debug("c = %d. index = %d.\n", c, *it);
					rbarrier = min(rbarrier, *it);
				}
				if (it != indc[c].begin()) {
					it--;
					lbarrier = max(lbarrier, *it);
				}
			}
			//lbarrier + 1
			bool ok = false;
			debug("-ok. lbarrier = %d. rbarrier = %d.-\n", lbarrier, rbarrier);
			int nl = lbarrier + 1, nr = rbarrier;
			debug("nl = %d, nr = %d\n", nl, nr);
			if (nl != L[i]) {
				L[i] = nl;
				//if there is something [nl, i]
				for (int c : vnohas) {
					auto it = lower_bound(all(indk[c]), nl);
					if (it != indk[c].end() && *it <= i) {
						has[c] = true;
					}
				}
				ok = true;
			}
			if (nr != R[i]) {
				R[i] = nr;

				//if there is something in [i, nr]
				for (int c : vnohas) {
					auto it = lower_bound(all(indk[c]), i);
					if (it != indk[c].end() && *it <= nr) {
						has[c] = true;
					}
				}
				ok = true;
			}

			//extend right, update colors which it has
			if (!ok) {
				break;
			}
		}
	}
}

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

	if (N <= 5000) {
		small();
	} else {
		large();
	}

	scanf("%d", &Q);
	//then let's do this stuff
	for (int i = 1; i <= Q; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		puts(L[x] <= y && y <= R[x] ? "YES" : "NO");
	}
}

Compilation message (stderr)

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:149:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
long_mansion.cpp:151:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &C[i]);
   ~~~~~^~~~~~~~~~~~~
long_mansion.cpp:155:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &b);
   ~~~~~^~~~~~~~~~
long_mansion.cpp:158:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &x);
    ~~~~~^~~~~~~~~~
long_mansion.cpp:168:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
long_mansion.cpp:172:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~~

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