Submission #1234784

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234784		PenguinsAreCute	Long Mansion (JOI17_long_mansion)	C++17	25 / 100	3097 ms	58772 KiB

long_mansion

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
struct seg {
	int n;
	vector<int> val;
	seg(int _n): n(_n), val(2*_n,-1e9) {}
	void up(int l, int r, int v) {
		for(l+=n,r+=n+1;l<r;l>>=1,r>>=1) {
			if(l&1) {
				val[l] = max(val[l], v);
				l++;
			}
			if(r&1) {
				r--;
				val[r] = max(val[r], v);
			}
		}
	}
	void prop() {
		for(int x=1;x<n;x++) {
			val[x<<1] = max(val[x<<1],val[x]);
			val[x<<1|1] = max(val[x<<1|1],val[x]);
		}
	}
	int qry(int x) {
		return val[x+n];
	}
};
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n;
	cin >> n;
	int c[n-1];
	for(int i=0;i<n-1;i++) {
		cin >> c[i]; 
		c[i]--;
	}
	vector<int> occ[n];
	for(int i=0;i<n;i++) {
		int b;
		cin >> b;
		for(int a;b--;) {
			cin >> a;
			occ[a-1].push_back(i);
		}
	}

	int f[n], g[n];
	vector<int>::iterator ptr[n];
	for(int i=0;i<n;i++)
		ptr[i] = occ[i].begin();
	for(int i=0;i<n;i++) {
		if(i==0)
			g[i] = n-1;
		else {
			while(ptr[c[i-1]] != occ[c[i-1]].end() && *ptr[c[i-1]] < i)
				ptr[c[i-1]]++;
			if(ptr[c[i-1]] == occ[c[i-1]].end())
				g[i] = n-1;
			else
				g[i] = *ptr[c[i-1]] - 1;
		}
		if(i==n-1)
			f[i] = 0;
		else {
			while(ptr[c[i]] != occ[c[i]].end() && *ptr[c[i]] <= i)
				ptr[c[i]]++;
			if(ptr[c[i]] == occ[c[i]].begin())
				f[i] = 0;
			else
				f[i] = *(ptr[c[i]]-1) + 1;
		}
	}
	vector<int> ginv[n], finv[n];
	for(int i=0;i<n;i++) {
		finv[f[i]].push_back(i);
		ginv[g[i]].push_back(i);
	}

	seg l(n), r(n);
	set<int> val;

	for(int lft=n;lft--;) {
		val.insert(lft);
		if(lft != n - 1)
			for(auto rgt: finv[lft + 1])
				if(val.find(rgt) != val.end())
					val.erase(rgt);
		auto it = upper_bound(val.begin(),val.end(),g[lft]);
		if(it != val.begin())
			l.up(lft, *--it, lft);
	}
	val.clear();

	for(int rgt=0;rgt<n;rgt++) {
		val.insert(rgt);
		if(rgt != 0)
			for(auto lft: ginv[rgt - 1])
				if(val.find(lft) != val.end())
					val.erase(lft);
		auto it = lower_bound(val.begin(),val.end(),f[rgt]);
		if(it != val.end())
			r.up(*it, rgt, -rgt);
	}

	l.prop();
	r.prop();

	int q;
	cin >> q;
	while(q--) {
		int x, y;
		cin >> x >> y;
		x--; y--;
		if(l.qry(x) <= y && y <= -r.qry(x))
			cout << "YES\n";
		else
			cout << "NO\n";
	}
}

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