Submission #21133

#	Time	Username	Problem	Language	Result	Execution time	Memory
21133		khsoo01	Long Mansion (JOI17_long_mansion)	C++11	100 / 100	469 ms	48576 KiB

long_mansion

#include<bits/stdc++.h>
using namespace std;
const int inf = 1e9;
int n, a[500005], l[500005], r[500005], lst[500005];
int q, xl[500005], xr[500005];
vector<int> st, ky[500005];

struct minseg {
	int val[1111111], lim;
	void init () {
		for(lim=1;lim<=n+1;lim<<=1);
		val[lim] = inf;
		for(int i=1;i<=n;i++) {
			val[lim + i] = l[i];
		}
		for(int i=lim;--i;) {
			val[i] = min(val[2*i], val[2*i+1]);
		}
	}
	void update (int P, int V) {
		P += lim;
		val[P] = V; P >>= 1;
		while(P) {
			val[P] = min(val[2*P], val[2*P+1]);
			P >>= 1;
		}
	}
	int query (int X, int SS, int SE, int P) {
		if(SS == SE) return SS;
		int mid = (SS+SE)/2;
		return (val[2*P] < X ? query(X, SS, mid, 2*P) : query(X, mid+1, SE, 2*P+1));
	}
	int query (int X) {return query(X, 0, lim-1, 1);}
} seg;

int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) {
		int M;
		scanf("%d",&M);
		for(int j=0;j<M;j++) {
			int tmp;
			scanf("%d",&tmp);
			ky[i].push_back(tmp);
		}
	}
	for(int i=1;i<n;i++) {
		for(auto &j : ky[i]) lst[j] = i;
		l[i+1] = lst[a[i]];
	}
	for(int i=1;i<=n;i++) lst[i] = n+1;
	r[n] = n+1;
	for(int i=n;i>1;i--) {
		for(auto &j : ky[i]) lst[j] = i;
		r[i-1] = lst[a[i-1]];
	}
	seg.init();
	for(int i=1;i<=n;i++) {
		xl[i] = i; xr[i] = i;
		seg.update(i, inf);
		while(true) {
			xr[i] = seg.query(xl[i]) - 1;
			if(xl[i] == 1 || r[xl[i]-1] > xr[i]) break;
			xl[i] = st.back(); st.pop_back();
		}
		st.push_back(xl[i]);
	}
	scanf("%d",&q);
	for(int i=1;i<=q;i++) {
		int A, B;
		scanf("%d%d",&A,&B);
		puts(xl[A] <= B && B <= xr[A] ? "YES" : "NO");
	}
}

Compilation message (stderr)

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:38:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
long_mansion.cpp:39:40: 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",&a[i]);
                                        ^
long_mansion.cpp:42:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&M);
                 ^
long_mansion.cpp:45:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&tmp);
                    ^
long_mansion.cpp:70:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
                ^
long_mansion.cpp:73:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&A,&B);
                      ^

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