Submission #125383

#	Time	Username	Problem	Language	Result	Execution time	Memory
125383		khsoo01	Long Mansion (JOI17_long_mansion)	C++11	100 / 100	447 ms	45136 KiB

long_mansion

#include<bits/stdc++.h>
using namespace std;

const int N = 500005, L = 524288;

int n, q, req[N], lst[N], rb[N], l[N], r[N];

vector<int> key[N];

struct segtree {
	int v[2*L];
	void upd (int P, int V) {
		P += L;
		v[P] = V;
		P /= 2;
		while(P) {
			v[P] = min(v[2*P], v[2*P+1]);
			P /= 2;
		}
	}
	int bound (int P, int V) {
		P += L;
		while(P & (P+1)) {
			if(v[P] < V) break;
			P = (P+1)/2;
		}
		while(P < L) {
			if(v[2*P] < V) P = 2*P;
			else P = 2*P+1;
		}
		return P - L;
	}
} seg;

int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++) {
		scanf("%d",&req[i]);
	}
	for(int i=1;i<=n;i++) {
		int M, T;
		scanf("%d",&M);
		while(M--) {
			scanf("%d",&T);
			key[i].push_back(T);
		}
	}
	for(int i=1;i<=n;i++) {
		seg.upd(i, lst[req[i-1]]);
		for(auto &T : key[i]) lst[T] = i;
	}
	fill(lst, lst+1+n, n+1);
	for(int i=n;i>=1;i--) {
		rb[i] = lst[req[i]];
		for(auto &T : key[i]) lst[T] = i;
	}
	vector<int> S;
	for(int i=1;i<=n;i++) {
		int L = i, R = seg.bound(i+1, L) - 1;
		while(!S.empty()) {
			if(rb[L-1] > R) break;
			L = S.back();
			R = seg.bound(i+1, L) - 1;
			S.pop_back();
		}
		l[i] = L, r[i] = R;
		S.push_back(L);
	}
	scanf("%d",&q);
	while(q--) {
		int S, E;
		scanf("%d%d",&S,&E);
		puts(l[S] <= E && E <= r[S] ? "YES" : "NO");
	}
}

Compilation message (stderr)

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
long_mansion.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&req[i]);
   ~~~~~^~~~~~~~~~~~~~
long_mansion.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&M);
   ~~~~~^~~~~~~~~
long_mansion.cpp:45:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&T);
    ~~~~~^~~~~~~~~
long_mansion.cpp:70:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
  ~~~~~^~~~~~~~~
long_mansion.cpp:73:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&S,&E);
   ~~~~~^~~~~~~~~~~~~~

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