Submission #718751

#	Time	Username	Problem	Language	Result	Execution time	Memory
718751		radal	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	316 ms	60400 KiB

long_mansion

#include <bits/stdc++.h>
//#pragma GCC target("sse,sse2,avx2")
#pragma GCC optimize("unroll-loops,O3")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
constexpr int N = 5e5+20,mod = 998244353;
constexpr ll inf = 1e18+10;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}
 
inline int poww(int a,int k){
    if (k < 0) return 0;
    int z = 1;
    while (k){
        if (k&1) z = 1ll*z*a%mod;
        a = 1ll*a*a%mod;
        k >>= 1;
    } 
    return z; 
}

int c[N],n;
vector<int> key[N];
bool st[N],en[N];
pll baz[N];

int par[N];

int getpar(int v){
	if (par[v] == v) return v;
	return par[v] = getpar(par[v]);
}

void mg(int u,int v){
	u = getpar(u);
	v = getpar(v);
	if (u == v) return;
	par[u] = v;
	baz[v].X = min(baz[u].X,baz[v].X);
    baz[v].Y = max(baz[u].Y,baz[v].Y);
}

void rlx(int v){
	st[v] = 1;
	baz[v] = {v,v};
	int l = v,r = v;
	while (1){
		bool fl = 0;
		while (r < n){
			int k = c[r];
			if (key[k].empty() || key[k].back() < l) break;
			int j = lower_bound(all(key[k]),l) - key[k].begin();
			if (key[k][j] > r) break;
			fl = 1;
			if (!st[r+1]){
			   	rlx(r+1);
				int p = getpar(r+1);
				r = max(r,baz[p].Y);
				l = min(l,baz[p].X);
				int p2 = getpar(v);
				baz[p2].X = min(l,baz[p2].X);
        	    baz[p2].Y = max(r,baz[p2].Y);
				baz[v] = baz[p2];
				l = baz[v].X;
				r = baz[v].Y;
				continue;
			}
			if (en[r+1]){
        	    int p = getpar(r+1);
            	r = max(r,baz[p].Y);
	            l = min(l,baz[p].X);
    	        int p2 = getpar(v);
        	    baz[p2].X = min(l,baz[p2].X);
            	baz[p2].Y = max(r,baz[p2].Y);
				baz[v] = baz[p2];
				l = baz[v].X;
				r = baz[v].Y;
				continue;
			}
			mg(v,r+1);
			int p = getpar(v);
			baz[v] = baz[p];
			l = baz[v].X;
			r = baz[v].Y;
		}
    	while (l > 1){
        	int k = c[l-1];
	        if (key[k].empty() || key[k].back() < l) break;
    	    int j = lower_bound(all(key[k]),l) - key[k].begin();
        	if (key[k][j] > r) break;
			fl = 1;
	        if (!st[l-1]){
    	        rlx(l-1);
        	    int p = getpar(l-1);
            	r = max(r,baz[p].Y);
	            l = min(l,baz[p].X);
    	        int p2 = getpar(v);
        	    baz[p2].X = min(l,baz[p2].X);
            	baz[p2].Y = max(r,baz[p2].Y);
	            baz[v] = baz[p2];
				l = baz[v].X;
				r = baz[v].Y;
            	continue;
	        }
    	    if (en[l-1]){
        	    int p = getpar(l-1);
            	int p2 = getpar(v);
	            baz[p2].X = min(baz[p].X,baz[p2].X);
    	        baz[p2].Y = max(baz[p].Y,baz[p2].Y);
        	    baz[v] = baz[p2];
				l = baz[v].X;
				r = baz[v].Y;
    	        continue;
        	}
 	       mg(v,l-1);
    	    int p = getpar(v);
        	baz[v] = baz[p];
	        l = baz[v].X;
    	    r = baz[v].Y;
	    }
		if (!fl) break;
	}
	en[v] = 1;
}

int main(){
	ios :: sync_with_stdio(0); cin.tie(0);  cout.tie(0);
	cin >> n;
	rep(i,1,n) cin >> c[i];
	rep(i,1,n+1){
		par[i] = i;
		int sz;
		cin >> sz;
		rep(j,0,sz){
			int t;
			cin >> t;
			key[t].pb(i);
		}
	}
	rep(i,1,n+1) if (!st[i]){
	   	rlx(i);
	}
	rep(i,1,n+1){
		int j = getpar(i);
		baz[i] = baz[j];
	}
	int q;
	cin >> q;
	while (q--){
		int x,y;
		cin >> x >> y;
		if (y >= baz[x].X && y <= baz[x].Y)
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}
} 

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