oj.uz

Submission #448307

# Submission time Handle Problem Language Result Execution time Memory
448307 2021-07-29T14:36:32 Z dutch Long Mansion (JOI17_long_mansion) C++17
0 / 100
 311 ms 33676 KB 
#include <bits/stdc++.h>
using namespace std;
#define f(z) z = n + 1 - z
 
const int LIM = 5e5+1, INF = 1e9, S = 1<<19;
 
struct SegmentTree{
	vector<int> a; int j, z;
	SegmentTree(int N, int* v) : a(S+S) {
		for(int i=N; --i>=0; ) a[i+S] = v[i];
		for(int i=S; --i; ){
			a[i] = max(a[2*i], a[2*i+1]);
		}
	}
	int rangeMax(int l, int r){
		int x = -INF;
		for(l+=S, r+=S+1; l<r; l/=2, r/=2){
			if(l & 1) x = max(x, a[l++]);
			if(r & 1) x = max(x, a[--r]);
		}
		return x;
	}
	int query(int x, int lx, int rx){
		if(a[x] <= z || rx <= z) return 0;
		if(rx - lx < 2) return lx;
		int mx = (lx + rx) / 2;
		return query(2*x, lx, mx) ? : query(2*x+1, mx, rx);
	}
	int operator()(int L, int V){ //first v[i] s.t. i>=l && v[i]>v
		j = L, z = V; return query(1, 0, S);
	}
};
 
int n, q, c[LIM], l[LIM], r[LIM], block[LIM];
array<int, 2> b[LIM];
bool ans[LIM];
vector<int> a[LIM];
 
void flip(){
	for(int i=1; i<n; ++i){
		f(l[i]), f(r[i]);
	}
	swap(l, r);
	reverse(l+1, l+n);
	reverse(r+1, r+n);
	for(int i=0; i<q; ++i){
		for(int &j : b[i]) f(j);
	}
}
 
void solve(){
	SegmentTree x(n, r);
	block[0] = 0;
	for(int i=1; i<n; ++i){
		block[i] = l[i] ? -min(n, x(l[i], i)) : 0;
	}
	SegmentTree y(n, block);
	
	for(int i=0; i<q; ++i){
		auto [u, v] = b[i];
		if(u < v) ans[i] = -y.rangeMax(u, v-1) >= u;
	}
}
 
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];
	}
 
	for(int i=1; i<n; ++i){
		for(int &j : a[i]) block[j] = i;
		l[i] = block[c[i]];
	}
	fill(block, block+n+1, n+1);
	for(int i=n; i>1; --i){
		for(int &j : a[i]) block[j] = i;
		r[i-1] = block[c[i-1]];
	}
	solve();
	flip();
	solve();

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 24388 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 24388 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 311 ms 33676 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 24388 KB Output isn't correct
2 Halted 0 ms 0 KB -