Submission #1080375

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080375		coldbr3w	Long Mansion (JOI17_long_mansion)	C++14	25 / 100	3066 ms	201672 KiB

long_mansion

#include <bits/stdc++.h>
using namespace std;
 
#define ll int
#define pll pair<int, int>
#define pb push_back
#define F first
#define S second  
#define all(x) (x).begin(), (x).end()
#define int long long
const ll N = 5e5 + 100;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll block = 230;
ll n, q;
ll c[N];
map<ll,ll>pos;
ll L[N][20], R[N][20], l[N], r[N], lg[N];
struct segment_tree_max{
    ll n;
    vector<ll>st;
    void init(ll _n){
        n = _n;
        st.clear(); st.resize(4 * n + 10, -inf);
    }
    void update(ll id, ll l, ll r, ll left, ll right, ll val){
        if(l > right || r < left) return;
        if(left <= l && r <= right){
            st[id] = max(st[id], val);
            return;
        }
        ll mid = (l + r) / 2;
        update(2 * id, l, mid, left, right, val);
        update(2 * id + 1, mid + 1, r, left, right, val);
        st[id] = max(st[2 * id], st[2 * id + 1]);
    }
    ll get(ll id, ll l, ll r, ll left, ll right){
        if(l > right || r < left) return -inf;
        if(left <= l && r <= right) return st[id];
        ll mid = (l + r) / 2;
        return max(get(2 * id, l, mid, left, right), get(2 * id + 1, mid + 1, r, left, right));
    }
    void update(ll l, ll r, ll val){update(1,1,n,l,r,val);}
    ll get(ll l, ll r){return get(1,1,n,l,r);}
} stmax;
struct segment_tree_min{
    ll n;
    vector<ll>st;
    void init(ll _n){
        n = _n;
        st.clear(); st.resize(4 * n + 10, inf);
    }
    void update(ll id, ll l, ll r, ll left, ll right, ll val){
        if(l > right || r < left) return;
        if(left <= l && r <= right){
            st[id] = min(st[id], val);
            return;
        }
        ll mid = (l + r) / 2;
        update(2 * id, l, mid, left, right, val);
        update(2 * id + 1, mid + 1, r, left, right, val);
        st[id] = min(st[2 * id], st[2 * id + 1]);
    }
    ll get(ll id, ll l, ll r, ll left, ll right){
        if(l > right || r < left) return inf;
        if(left <= l && r <= right) return st[id];
        ll mid = (l + r) / 2;
        return min(get(2 * id, l, mid, left, right), get(2 * id + 1, mid + 1, r, left, right));
    }
    void update(ll l, ll r, ll val){update(1,1,n,l,r,val);}
    ll get(ll l, ll r){return get(1,1,n,l,r);}
} stmin;
vector<ll>g[N];
ll get_L(ll l, ll r){
	ll p = lg[r - l + 1];
	return min(L[l][p], L[r - (1 << p) + 1][p]);
}
ll get_R(ll l, ll r){
	ll p = lg[r - l + 1];
	return max(R[l][p], R[r - (1 << p) + 1][p]);
}
void build(){
	for(int i = 1; i <= n;i++){
		if(i >= 2) L[i][0] = (pos[c[i - 1]] == 0 ? -inf : pos[c[i-1]]);
		else L[i][0] = -inf;
		for(auto x : g[i]) pos[x] = i;
	}
	pos.clear();
	for(int i = n; i >= 1;i--){
		if(i <= n - 1) R[i][0] = (pos[c[i]] == 0 ? inf : pos[c[i]]);
		else R[i][0] = inf;
		for(auto x : g[i]) pos[x] = i;
	}
	for(int j = 1; j <= 19;j++){
		for(int i = 1; i + (1 << j) <= n + 1;i++){
			L[i][j] = min(L[i][j-1], L[i + (1 << (j - 1))][j-1]);
			R[i][j] = max(R[i][j-1], R[i + (1 << (j - 1))][j-1]);
		}
	}
	for(int i = 1; i <= n;i++){
		ll x = i, y = i;
		while(1){
			pll lst = {x, y};
			if(x > 1){
				ll l = 1, r = x - 1, pos = -1;
				while(l <= r){
					ll mid = (l + r) / 2;
					if(get_R(mid, x - 1) <= y) pos = mid, r = mid - 1;
					else l = mid + 1;
				}
				if(pos != -1){
					ll mn = stmin.get(pos, y), mx = stmax.get(pos, y); 
					x = min({x, mn, pos}); y = max(y, mx);
				}
			}
			if(y < n){
				ll l = y + 1, r = n, pos = -1;
				while(l <= r){
					ll mid = (l + r) / 2;
					if(get_L(y + 1, mid) >= x) pos = mid, l = mid + 1;
					else r = mid - 1;
				}
				if(pos != -1){
					ll mn = stmin.get(x, pos), mx = stmax.get(x, pos); 
					x = min(x, mn); y = max({y, mx, pos});
				}	
			}
			if(lst.F == x && lst.S == y) break;	
		}
		l[i] = x, r[i] = y;
		stmin.update(i, i, l[i]); stmax.update(i, i, r[i]);
	}
}
void to_thic_cau(){
	cin >> n;
	for(int i = 1; i <= n;i++) lg[i] = __lg(i);
	for(int i = 1; i <= n - 1;i++) cin >> c[i];
	for(int i = 1; i <= n;i++){
		ll sz; cin >> sz;
		for(int j = 1; j <= sz;j++){
			ll x; cin >> x;
			g[i].pb(x);
		}
	}
	build();
	cin >> q;
	while(q--){
		ll x,y; cin >> x >> y;
		if(l[x] <= y && y <= r[x]) cout << "YES" << '\n';
		else cout << "NO" << "\n";
	}
}
 
signed main()   
{  
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll tc = 1;
	//cin >> tc;
	while(tc--) to_thic_cau();
}

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