Submission #125488

#	Time	Username	Problem	Language	Result	Execution time	Memory
125488		imyujin	Long Mansion (JOI17_long_mansion)	C++14	100 / 100	1192 ms	142208 KiB

long_mansion

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

#define MAXN 500005

int N;
vector<int> A[MAXN];
int B[MAXN], C[MAXN], X[MAXN], Y[MAXN];
int left[MAXN], rig[MAXN], lefinv[MAXN], riginv[MAXN];
int L[MAXN], R[MAXN], Rinv[MAXN];
int lastkey[MAXN], sparse[20][MAXN];
vector<int> mn[MAXN], mnt[MAXN];

void findleft(vector<int> A[], int C[], int left[]) {
	for(int i = 1; i <= N; i++) lastkey[i] = 0;
	for(int i = 1; i < N; i++) {
		for(auto a : A[i]) lastkey[a] = i;
		left[i] = lastkey[C[i]];
	}
	left[0] = left[N] = 0;
}

void setL(int left[], int rig[], int L[]) {
	priority_queue<int> pq, pqt;

	for(int i = 0; i <= N; i++) sparse[0][i] = left[i];
	for(int i = 1; i < 20; i++) for(int j = (1 << i) - 1; j <= N; j++)
		sparse[i][j] = min(sparse[i - 1][j], sparse[i - 1][j - (1 << i - 1)]);

	for(int i = 1; i <= N; i++) {
		mn[i].clear();
		mnt[i].clear();
	}
	for(int i = 0; i <= N; i++) {
		int t = rig[i] - 1;
		for(int j = 19; j >= 0; j--) if(t - (1 << j) + 1 >= 0 && sparse[j][t] > i) t -= (1 << j);
		t = max(t, i);
		mn[i + 1].push_back(i + 1);
		mnt[t + 1].push_back(i + 1);
	}
	for(int i = 1; i <= N; i++) {
		for(auto a : mn[i]) pq.push(a);
		for(auto a : mnt[i]) pqt.push(a);
		while(!pqt.empty() && pq.top() == pqt.top()) {
			pq.pop();
			pqt.pop();
		}
		L[i] = pq.top();
	}
}

int main() {
	int Q;

	scanf("%d", &N);
	for(int i = 1; i < N; i++) scanf("%d", C + i);
	for(int i = 1; i <= N; i++) {
		scanf("%d", B + i);
		for(int j = 0; j < B[i]; j++) {
			int t;
			scanf("%d", &t);
			A[i].push_back(t);
		}
	}
	scanf("%d", &Q);
	for(int i = 0; i < Q; i++) scanf("%d%d", X + i, Y + i);

	findleft(A, C, left);
	for(int i = 1; i <= N / 2; i++) swap(A[i], A[N - i + 1]);
	for(int i = 1; i <= (N - 1) / 2; i++) swap(C[i], C[N - i]);
	findleft(A, C, lefinv);
	for(int i = 0; i <= N; i++) {
		rig[i] = N - lefinv[N - i] + 1;
		riginv[i] = N - left[N - i] + 1;
	}

	setL(left, rig, L);
	setL(lefinv, riginv, Rinv);
	for(int i = 1; i <= N; i++) R[i] = N - Rinv[N - i + 1] + 1;

	for(int i = 0; i < Q; i++) {
		if(L[X[i]] <= Y[i] && Y[i] <= R[X[i]]) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}

Compilation message (stderr)

long_mansion.cpp: In function 'void setL(int*, int*, int*)':
long_mansion.cpp:32:66: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   sparse[i][j] = min(sparse[i - 1][j], sparse[i - 1][j - (1 << i - 1)]);
                                                                ~~^~~
long_mansion.cpp: In function 'int main()':
long_mansion.cpp:59:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
long_mansion.cpp:60:34: 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:62: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:65:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &t);
    ~~~~~^~~~~~~~~~
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:70:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 0; i < Q; i++) scanf("%d%d", X + i, Y + i);
                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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