Submission #1234929

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234929		salmon	Long Mansion (JOI17_long_mansion)	C++20	100 / 100	782 ms	137644 KiB

long_mansion

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

int N;
int Q;
int lst[500100];
int B[500100];
vector<int> pos[500100];
int l[500100];
int r[500100];
int ml[500100];
int mr[500100];

struct fode{
	
	int s, e, m;
	int vl;
	int vr;
	fode *l, *r;
	
	fode(int S, int E){
		s = S;
		e = E;
		m = (s + e)/2;
	
		if(s == e){
			vl = ml[s];
			vr = mr[s];
		}
		else{
			l = new fode(s,m);
			r = new fode(m + 1, e);
			
			vl = min(l -> vl, r -> vl);
			vr = max(l -> vr, r -> vr);
		}
	}
	
	int queryl(int S, int E){
		if(S <= s && e <= E){
			return vl;
		}
		
		int V = N + 1;
		if(S <= m) V = min(V, l -> queryl(S,E));
		if(m < E) V = min(V, r -> queryl(S,E));
		
		return V;
	}	
	
	
	int queryr(int S,int E){
		if(S <= s && e <= E){
			return vr;
		}
		
		int V = 0;
		
		if(S <= m) V = max(V, l -> queryr(S,E));
		if(m < E) V = max(V, r-> queryr(S,E));
		
		return V;
	}
	
}*foot;

struct node{
		
	int s, e, m;
	int vl;
	int vr;
	node *l, *r;

	node(int S, int E){
		s = S;
		e = E;
		m = (s + e)/2;
		
		if(s != e){
			l = new node(s,m);
			r = new node(m + 1, e);
			
			vl = min(l -> vl, r -> vl);
			vr = max(l -> vr, r -> vr);
		}
		else{
			vl = ::l[m];
			vr = ::r[m];
		}
	}
	
	int queryl(int S, int E, int k){
		if(E < S) return -1;
		
		if(S <= s && e <= E){
			if(vl > k) return -1;
			if(s == e) return s;
			if(r -> vl <= k) return r -> queryl(S,E,k);
			else return l -> queryl(S,E,k);
		}
		
		if(m < E){
			int v = r -> queryl(S,E,k);
			if(v != -1) return v;
		}
		if(S <= m) return l -> queryl(S,E,k);
		return -1; 
	}
	
	int queryr(int S ,int E, int k){
		if(E < S) return -1;
		
		if(S <= s && e <= E){
			if(vr < k) return -1;
			if(s == e) return s;
			if(l -> vr >= k) return l -> queryr(S,E,k);
			else return r -> queryr(S,E,k);
		}
		
		if(S <= m){
			int v = l -> queryr(S,E,k);
			if(v != -1) return v;
		}
		if(m < E) return r -> queryr(S,E,k);
		return -1;
	}
}*root;

int main(){
	
	scanf(" %d",&N);
	
	for(int i = 1; i <= N - 1; i++){
		scanf(" %d",&lst[i]);
	}

	for(int i = 1; i <= N; i++){
		pos[i].push_back(0);
	}
	
	for(int i = 1; i <= N; i++){
		scanf(" %d",&B[i]);
		
		for(int j = 0; j < B[i]; j++){
			int h;
			scanf(" %d",&h);
			
			pos[h].push_back(i);
		}
	}
	
	for(int i = 1; i <= N; i++) pos[i].push_back(N + 1);
	
	l[0] = 0;
	r[0] = N + 1;
	l[N + 1] = N+1;
	r[N + 1] = 0;
	
	for(int i = 1; i <= N; i++){
		if(i != 1){
			int t = lst[i - 1];		
			l[i] = pos[t][lower_bound(pos[t].begin(), pos[t].end(), i) - pos[t].begin() - 1];
		}
		else{
			l[i] = 0;
		}
		
		if(i != N){
			int t = lst[i];
			r[i] = pos[t][upper_bound(pos[t].begin(), pos[t].end(), i) - pos[t].begin()];
		}
		else{
			r[i] = N;
		}
	}	
	
	root = new node(0,N + 1);
	
	for(int i = 1; i <= N; i++){
		if(l[i] == 0) ml[i] = 0;
		else ml[i] = root -> queryr( l[i],i - 1, i);
		if(r[i] == N + 1) mr[i] = N + 1;
		else mr[i] = root -> queryl( i + 1, r[i], i);
		
		if(ml[i] == -1) ml[i] = i;
		if(mr[i] == -1) mr[i] = i;
		
		//printf("%d %d\n",ml[i],mr[i]);
	}
	
	foot = new fode(1,N);
	
	scanf(" %d",&Q);
	
	for(int i = 0; i < Q; i++){
		int X,Y;
		
		scanf(" %d",&X);
		scanf(" %d",&Y);

		if(X < Y){
			bool can = (foot -> queryl(X+1,Y) >= X);
			
			if(can) printf("YES\n");
			else printf("NO\n");
		}
		else{
			bool can = (foot -> queryr(Y,X-1) <= X);
			
			if(can) printf("YES\n");
			else printf("NO\n");
		}
	}
}

Compilation message (stderr)

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:131:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |         scanf(" %d",&N);
      |         ~~~~~^~~~~~~~~~
long_mansion.cpp:134:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |                 scanf(" %d",&lst[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~
long_mansion.cpp:142:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |                 scanf(" %d",&B[i]);
      |                 ~~~~~^~~~~~~~~~~~~
long_mansion.cpp:146:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  146 |                         scanf(" %d",&h);
      |                         ~~~~~^~~~~~~~~~
long_mansion.cpp:193:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  193 |         scanf(" %d",&Q);
      |         ~~~~~^~~~~~~~~~
long_mansion.cpp:198:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  198 |                 scanf(" %d",&X);
      |                 ~~~~~^~~~~~~~~~
long_mansion.cpp:199:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  199 |                 scanf(" %d",&Y);
      |                 ~~~~~^~~~~~~~~~

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