Submission #23620

#	Time	Username	Problem	Language	Result	Execution time	Memory
23620		rubabredwan	Long Mansion (JOI17_long_mansion)	C++14	100 / 100	576 ms	50988 KiB

long_mansion

/*  Bismillahir Rahmanir Rahim  */

#include <bits/stdc++.h>

using namespace std;

const int N = 500005;

int n, lf[N], rf[N], C[N];
int past[N], t[N*4];
int L[N], R[N];
vector<int>A[N];

void build(int l, int r, int id){
	if(l == r){
		t[id] = lf[l];
		return;
	}
	int mid = (l + r) / 2;
	build(l, mid, id + id);
	build(mid + 1, r, id + id + 1);
	t[id] = min(t[id + id], t[id + id + 1]);
}

int get(int l, int r, int id, int val){
	if(t[id] >= val) return n + 1;
	if(l == r) return l;
	int mid = (l + r) / 2;
	if(t[id + id] < val) return get(l, mid, id + id, val);
	else return get(mid + 1, r, id + id + 1, val);
}

void update(int l, int r, int id, int pos){
	if(l == r){
		t[id] = n + 1;
		return;
	}
	int mid = (l + r) / 2;
	if(pos <= mid) update(l, mid, id + id, pos);
	else update(mid + 1, r, id + id + 1, pos);
	t[id] = min(t[id + id], t[id + id + 1]);
}

void init(){
	for(int i = 0; i < N; i++) past[i] = 0;
	for(int i = 1; i <= n; i++){
		lf[i] = past[ C[i] ];
		for(auto u : A[i]){
			past[u] = i;
		}
	}
	for(int i = 0; i < N; i++) past[i] = n + 1;
	for(int i = n; i >= 1; i--){
		for(auto u : A[i]){
			past[u] = i;
		}
		rf[i] = past[ C[i] ];
	}
	build(1, n, 1);
}

void solve(){
	stack<int>S;
	for(int i = 1; i <= n; i++){
		L[i] = R[i] = i;
		update(1, n, 1, i);
		while(1){
			R[i] = get(1, n, 1, L[i]) - 1;
			if(L[i] == 1) break;
			if(rf[ L[i] ] > R[i]) break;
			L[i] = S.top(); S.pop();
		}
		S.push(L[i]);
	}
}

int main(){
	int q, x, y;
	scanf("%d", &n);
	for(int i = 2; i <= n; i++) scanf("%d", &C[i]);
	for(int i = 1; i <= n; i++){
		scanf("%d", &x);
		while(x--){
			scanf("%d", &y);
			A[i].push_back(y);
		}
	}
	init();
	solve();
	scanf("%d", &q);
	while(q--){
		scanf("%d %d", &x, &y);
		if(L[x] <= y && y <= R[x]) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}

Compilation message (stderr)

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:79:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
long_mansion.cpp:80:48: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 2; i <= n; i++) scanf("%d", &C[i]);
                                                ^
long_mansion.cpp:82:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
                  ^
long_mansion.cpp:84:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &y);
                   ^
long_mansion.cpp:90:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
                 ^
long_mansion.cpp:92:25: 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: 75 / 75