Submission #1234914

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234914		salmon	Long Mansion (JOI17_long_mansion)	C++20	10 / 100	3096 ms	30572 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 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]);
	}
	
	scanf(" %d",&Q);
	
	for(int i = 0; i < Q; i++){
		int X,Y;
		
		scanf(" %d",&X);
		scanf(" %d",&Y);
		
		if(X < Y){
			bool can = true;
			
			for(int i = X + 1; i <= Y; i++){
				if(ml[i] < X){
					can = false;
					break;
				}
			}
			
			if(can) printf("YES\n");
			else printf("NO\n");
		}
		else{
			bool can = true;
			
			for(int i = X - 1; i >= Y; i--){
				if(mr[i] > X){
					can = false;
					break;
				}
			}
			
			if(can) printf("YES\n");
			else printf("NO\n");
		}
	}
}

Compilation message (stderr)

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:78:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         scanf(" %d",&N);
      |         ~~~~~^~~~~~~~~~
long_mansion.cpp:81:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |                 scanf(" %d",&lst[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~
long_mansion.cpp:89:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |                 scanf(" %d",&B[i]);
      |                 ~~~~~^~~~~~~~~~~~~
long_mansion.cpp:93:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |                         scanf(" %d",&h);
      |                         ~~~~~^~~~~~~~~~
long_mansion.cpp:138:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  138 |         scanf(" %d",&Q);
      |         ~~~~~^~~~~~~~~~
long_mansion.cpp:143:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  143 |                 scanf(" %d",&X);
      |                 ~~~~~^~~~~~~~~~
long_mansion.cpp:144:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |                 scanf(" %d",&Y);
      |                 ~~~~~^~~~~~~~~~

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