Submission #447986

#	Time	Username	Problem	Language	Result	Execution time	Memory
447986		dutch	Long Mansion (JOI17_long_mansion)	C++17	0 / 100	311 ms	39320 KiB

long_mansion

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

const int LIM = 5e5+1, INF = 1e9;

struct SegmentTree{
	vector<int> a; int s = 1, l, r, c;
	SegmentTree(vector<int> &v){
		while((s+=s)<(int)size(v));
		a.resize(2*s, INF);
		for(int i=(int)size(v); --i>=0; ){
			a[i+s-1] = v[i];
		}
		for(int i=s-1; --i>=0; ){
			a[i] = min(a[2*i+1], a[2*i+2]);
		}
	}
	int query(int x, int lx, int rx){
		if(a[x] >= c || rx <= c) return 0;
		if(rx - lx < 2) return lx;
		int mx = (lx + rx) / 2;
		return query(2*x+1, lx, mx) ? : query(2*x+2, mx, rx);
	}
	int operator()(int C){
		c = C; return query(0, 0, s);
	}
	int rangeMin(int x, int lx, int rx){
		if(r<=lx || rx<=l) return INF;
		if(l<=lx && rx<=r) return a[x];
		int mx = (lx + rx) / 2;
		return min(rangeMin(2*x+1, lx, mx), rangeMin(2*x+2, mx, rx));
	}
	int rangeMin(int L, int R){
		l = L, r = R + 1; return rangeMin(0, 0, s);
	}
};

int n, q, c[LIM], last[LIM], l[LIM], r[LIM];
array<int, 2> b[LIM];
bool ans[LIM];
vector<int> a[LIM], rL(LIM+1), rR(LIM+1);

void flip(){
	for(int i=1; i<n; ++i){
		l[i] = n + 1 - l[i];
		r[i] = n + 1 - r[i];
	}
	swap(l, r);
	for(int i=1; i+i<n; ++i){
		swap(l[i], l[n-i]);
		swap(r[i], r[n-i]);
	}
	for(int i=1; i<=n; ++i){
		rL[i] = n + 1 - rL[i];
		rR[i] = n + 1 - rR[i];
	}
	swap(rL, rR);
	for(int i=1; i+i<n+1; ++i){
		swap(rL[i], rL[n+1-i]);
		swap(rR[i], rR[n+1-i]);
	}
	for(int i=0; i<q; ++i){
		for(int &j : b[i]) j = n + 1 - j;
	}
}

void reach(vector<int> &v){
	for(int i=1; i<n; ++i) v[i] = l[i];
	SegmentTree st(v);
	for(int i=1; i<=n; ++i) v[i] = min(n, st(i));
}

void solve(){
	vector<int> z(n+1);
	for(int i=1; i<n; ++i) z[i] =-r[i];
	SegmentTree maxR(z);

	int blocked[n+1];
	blocked[1] = 1;

	for(int i=2; i<n; ++i){
		blocked[i] = !l[i] || -maxR.rangeMin(l[i], l[i-1]-1) > i;
		blocked[i] += blocked[i-1];
	}
	
	for(int i=0; i<q; ++i){
		auto [u, v] = b[i];
		if(u > v) continue;
		int x = rL[u], y = rR[u];
		if(x != y){
			bool init = !l[y] || -maxR.rangeMin(l[y], x-1) > y;
			ans[i] = y >= v || !(blocked[v-1]-blocked[y] || init);
		}
	}
}

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> n;
	for(int i=1; i<n; ++i) cin >> c[i];
	for(int i=1, j; i<=n; ++i){
		cin >> j;
		a[i].resize(j);
		for(int &k : a[i]) cin >> k;
	}

	cin >> q;
	for(int i=0; i<q; ++i){
		cin >> b[i][0] >> b[i][1];
	}

	fill(last, last+n+1, 0);
	for(int i=1; i<n; ++i){
		for(int &j : a[i]) last[j] = i;
		l[i] = last[c[i]];
	}
	fill(last, last+n+1, n+1);
	for(int i=n; i>1; --i){
		for(int &j : a[i]) last[j] = i;
		r[i-1] = last[c[i-1]];
	}
	reach(rR);
	flip();
	reach(rR);

	solve();
	flip();
	solve();
	for(int i=0; i<q; ++i){
		cout << (ans[i] ? "YES" : "NO") << '\n';
	}
}

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