Submission #697103

#	Time	Username	Problem	Language	Result	Execution time	Memory
697103		amunduzbaev	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	689 ms	144512 KiB

long_mansion

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

#define ar array
typedef long long ll;
//~ #define int ll

const int N = 5e5 + 5;
int c[N], b[N], last[N];
vector<int> a[N];
int l[N], r[N];
int L[N], R[N];
int mn[N][20], mx[N][20];

struct ST{
	int L[N << 2], R[N << 2];
	ST(){
		memset(R, 63, sizeof R);
	}
	
	void umin(int l, int r, int v, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return;
		if(lx >= l && rx <= r){
			R[x] = min(R[x], v);
			return;
		}
		int m = (lx + rx) >> 1;
		umin(l, r, v, lx, m, x << 1);
		umin(l, r, v, m + 1, rx, x << 1 | 1);
	}
	
	void umax(int l, int r, int v, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return;
		if(lx >= l && rx <= r){
			L[x] = max(L[x], v);
			return;
		}
		int m = (lx + rx) >> 1;
		umax(l, r, v, lx, m, x << 1);
		umax(l, r, v, m + 1, rx, x << 1 | 1);
	}
	
	ar<int, 2> get(int i, int lx = 0, int rx = N, int x = 1){
		if(lx == rx) return {L[x], R[x]};
		int m = (lx + rx) >> 1;
		ar<int, 2> res {};
		if(i <= m){
			res = get(i, lx, m, x << 1);
		} else {
			res = get(i, m + 1, rx, x << 1 | 1);
		}
		res[0] = max(res[0], L[x]);
		res[1] = min(res[1], R[x]);
		return res;
	}
}tree;

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin >> n;
	for(int i=1;i<n;i++){
		cin >> c[i];
	}
	
	for(int i=1;i<=n;i++){
		cin >> b[i];
		L[i] = 1, R[i] = n;
		a[i].resize(b[i]);
		for(int j=0;j<b[i];j++){
			cin >> a[i][j];
		}
	}
	
	for(int i=0;i<N;i++) last[i] = 0;
	for(int i=1;i<=n;i++){
		for(auto x : a[i]){
			last[x] = i;
		}
		l[i] = last[c[i]];
	}
	for(int i=0;i<N;i++) last[i] = n + 1;
	for(int i=n;i>0;i--){
		r[i] = last[c[i]];
		for(auto x : a[i]){
			last[x] = i;
		}
	}
	r[0] = N, l[n] = 0;
	
	for(int i=0;i<=n;i++){
		mx[i][0] = r[i]; // r[i]
		mn[i][0] = l[i]; // l[i]
	}
	for(int j=1;j<20;j++){
		for(int i=0;i + (1 << (j - 1)) <= n;i++){
			mx[i][j] = max(mx[i][j-1], mx[i + (1 << (j - 1))][j-1]);
			mn[i][j] = min(mn[i][j-1], mn[i + (1 << (j - 1))][j-1]);
		}
	}
	
	auto get_mn = [&](int l_, int r_){
		int lg = __lg(r_ - l_ + 1);
		return min(mn[l_][lg], mn[r_ - (1 << lg) + 1][lg]);
	};
	auto get_mx = [&](int l_, int r_){
		int lg = __lg(r_ - l_ + 1);
		return max(mx[l_][lg], mx[r_ - (1 << lg) + 1][lg]);
	};
	
	for(int i=1;i<n;i++){
		{
			//~ int j = get_mn(i, r[i] - 1);
			int l_ = i + 1, r_ = r[i] - 1;
			while(l_ < r_){
				int m = (l_ + r_ + 1) >> 1;
				if(get_mn(m, r[i] - 1) <= i){
					l_ = m;
				} else {
					r_ = m - 1;
				}
			}
			int j = l_;
			if(l_ == r_ && l[j] <= i){
				tree.umax(i + 1, j, i + 1);
			}
		}
		
		{
			//~ int j = get_mx(l[i], i);
			int l_ = l[i], r_ = i - 1;
			while(l_ < r_){
				int m = (l_ + r_ ) >> 1;
				if(get_mx(l[i], m) > i){
					r_ = m;
				} else {
					l_ = m + 1;
				}
			}
			
			int j = l_;
			if(l_ == r_ && i < r[j]){
				tree.umin(j + 1, i, i);
			}
		}
	}
	
	for(int i=1;i<=n;i++){
		auto res = tree.get(i);
		L[i] = max(L[i], res[0]);
		R[i] = min(R[i], res[1]);
	}
	
	int q; cin >> q;
	while(q--){
		int a, b; cin >> a >> b;
		if(L[a] <= b && b <= R[a]){
			cout<<"YES\n";
		} else {
			cout<<"NO\n";
		}
	}
}

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