Submission #139386

#TimeUsernameProblemLanguageResultExecution timeMemory
139386dndhkLong Mansion (JOI17_long_mansion)C++14
25 / 100
3024 ms87572 KiB
#include <bits/stdc++.h>

#define pb push_back
#define all(v) ((v).begin(), (v).end())
#define sortv(v) sort(all(v))
#define sz(v) ((int)(v).size())
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define umax(a, b) (a)=max((a), (b))
#define umin(a, b) (a)=min((a), (b))
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define rep(i,n) FOR(i,1,n)
#define rep0(i,n) FOR(i,0,(int)(n)-1)
#define FI first
#define SE second
#define INF 2000000000
#define INFLL 1000000000000000000LL


using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAX_N = 500000;


int N, Q;
int C[MAX_N+1];
int L[MAX_N+1], R[MAX_N+1];
int L2[MAX_N+1], R2[MAX_N+1];
map<int, int> mp;
vector<int> key[MAX_N+1];


struct SEG{
	struct NODE{
		NODE(int l, int r, int mx, int mn) : l(l), r(r), mx(mx) , mn(mn){}
		int l, r;
		int mx, mn;
		// int sum, mn;
	};
	int SZ;
	vector<NODE> seg;
	void Init(int x){
		SZ = x;
		seg.pb({-1, -1, 0, INF});
		init(0, 1, SZ);
	}

	void init(int idx, int s, int e){
		if(s==e)	return;
		seg[idx].l = seg.size(); seg.pb({-1, -1, 0, INF});
		seg[idx].r = seg.size(); seg.pb({-1, -1, 0, INF});
		init(seg[idx].l, s, (s+e)/2);
		init(seg[idx].r, (s+e)/2+1, e);
	}
	void Update(int x, int y){
		update(0, 1, SZ, x, y);
	}
	void update(int idx, int s, int e, int x, int y){
		seg[idx].mx = std::max(seg[idx].mx, y);
		seg[idx].mn = std::min(seg[idx].mn, y);
		if(s==e)	return;
		if(x<=(s+e)/2){
			update(seg[idx].l, s, (s+e)/2, x, y);
		}else{
			update(seg[idx].r, (s+e)/2+1, e, x, y);
		}
	}
	int Max(int x, int y){
		return max(0, 1, SZ, x, y);
	}
	int max(int idx, int s, int e, int x, int y){
		if(x<=s && e<=y)	return seg[idx].mx;
		if(x>e || y<s)	return 0;
		return std::max(max(seg[idx].l, s, (s+e)/2, x, y), max(seg[idx].r, (s+e)/2+1, e, x, y));
	}
	int Min(int x, int y){
		return min(0, 1, SZ, x, y);
	}
	int min(int idx, int s, int e, int x, int y){
		if(x<=s && e<=y)	return seg[idx].mn;
		if(x>e || y<s)	return INF;
		return std::min(min(seg[idx].l, s, (s+e)/2, x, y), min(seg[idx].r, (s+e)/2+1, e, x, y));
	}
};

SEG Seg1, Seg2, Seg3, Seg4;

void makeLR(){
	for(int i=1; i<N; i++){
		for(int j : key[i])	mp[j] = i;
		if(mp[C[i]]==0){
			L[i] = -1;
			Seg1.Update(i, 0);

		}else{
			L[i] = mp[C[i]];
			Seg1.Update(i, L[i]);
		}
	}
	for(int i=1; i<N; i++){	
		for(int j : key[i]){
			mp[j] = 0;
		}
	}
	for(int i=N-1; i>0; i--){
		for(int j : key[i+1])	mp[j] = i+1;
		if(mp[C[i]]==0){
			R[i] = -1;
			Seg2.Update(i, N);
		}else{
			R[i] = mp[C[i]];
			Seg2.Update(i, R[i]);
		}
	}	
}

void printLR(){
	for(int i=1; i<N; i++){
		cout<<i<<" "<<L[i]<<" "<<R[i]<<endl;
	}
}

void makeLR2(){
	for(int i=1; i<N; i++){
		if(L[i]==-1){
			L2[i] = 0;
		}else{
			int s = L[i], e = i, m;
			while(s<e){
				m = (s+e)/2;
				if(Seg2.Max(L[i], m) > i){
					e = m;
				}else{
					s = m+1;
				}
			}
			L2[i] = s;
		}
		if(R[i]==-1){
			R2[i] = INF;
		}else{
			int s = i, e = R[i]-1, m;
			while(s<e){
				m = (s+e)/2+1;
				if(Seg1.Min(m, R[i]-1) <= i){
					s = m;
				}else{
					e = m-1;
				}
			}
			R2[i] = s+1;
		}
		Seg3.Update(i, L2[i]);
		Seg4.Update(i, R2[i]);
	}
}

void printLR2(){
	for(int i=1; i<N; i++){
		cout<<i<<" "<<L2[i]<<" "<<R2[i]<<endl;
	}
}

int main(){
	scanf("%d", &N);
	Seg1.Init(N), Seg2.Init(N);
	Seg3.Init(N), Seg4.Init(N);
	for(int i=1; i<=N-1; i++){
		scanf("%d", &C[i]);
	}
	for(int i=1; i<=N; i++){
		int x, y;
		scanf("%d", &x);
		while(x--){
			scanf("%d", &y);
			key[i].pb(y);
		}
	}
	makeLR();
	//printLR();
	makeLR2();
	//printLR2();
	scanf("%d", &Q);
	while(Q--){
		int x, y;
		scanf("%d%d", &x, &y);
		if(x<y){
			int t = Seg3.Min(x, y-1);
			if(t<x){
				printf("NO\n");
			}else{
				printf("YES\n");
			}
		}else{
			int t = Seg4.Max(y, x-1);
			if(t>x){
				printf("NO\n");
			}else{
				printf("YES\n");
			}
		}
	}
	return 0;
}

Compilation message (stderr)

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:167:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
long_mansion.cpp:171:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &C[i]);
   ~~~~~^~~~~~~~~~~~~
long_mansion.cpp:175:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
   ~~~~~^~~~~~~~~~
long_mansion.cpp:177:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &y);
    ~~~~~^~~~~~~~~~
long_mansion.cpp:185:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
long_mansion.cpp:188:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...