oj.uz

Submission #718751

# Submission time Handle Problem Language Result Execution time Memory
718751 2023-04-04T17:00:02 Z radal Long Mansion (JOI17_long_mansion) C++17
100 / 100
 316 ms 60400 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12116 KB Output is correct
2 Correct 8 ms 12372 KB Output is correct
3 Correct 9 ms 12560 KB Output is correct
4 Correct 8 ms 12244 KB Output is correct
5 Correct 8 ms 12408 KB Output is correct
6 Correct 9 ms 12252 KB Output is correct
7 Correct 9 ms 12184 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12116 KB Output is correct
2 Correct 8 ms 12372 KB Output is correct
3 Correct 9 ms 12560 KB Output is correct
4 Correct 8 ms 12244 KB Output is correct
5 Correct 8 ms 12408 KB Output is correct
6 Correct 9 ms 12252 KB Output is correct
7 Correct 9 ms 12184 KB Output is correct
8 Correct 108 ms 18132 KB Output is correct
9 Correct 103 ms 17996 KB Output is correct
10 Correct 106 ms 18412 KB Output is correct
11 Correct 106 ms 18880 KB Output is correct
12 Correct 99 ms 17644 KB Output is correct
13 Correct 101 ms 18188 KB Output is correct
14 Correct 106 ms 18196 KB Output is correct
15 Correct 107 ms 18212 KB Output is correct
16 Correct 96 ms 18136 KB Output is correct
17 Correct 106 ms 18124 KB Output is correct
18 Correct 112 ms 18192 KB Output is correct
19 Correct 107 ms 18288 KB Output is correct
20 Correct 98 ms 18408 KB Output is correct
21 Correct 101 ms 18128 KB Output is correct
22 Correct 106 ms 18220 KB Output is correct
23 Correct 111 ms 18124 KB Output is correct
24 Correct 101 ms 18096 KB Output is correct
25 Correct 102 ms 17996 KB Output is correct
26 Correct 101 ms 17956 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 24224 KB Output is correct
2 Correct 186 ms 26508 KB Output is correct
3 Correct 186 ms 28472 KB Output is correct
4 Correct 181 ms 26116 KB Output is correct
5 Correct 178 ms 26328 KB Output is correct
6 Correct 159 ms 27448 KB Output is correct
7 Correct 153 ms 31828 KB Output is correct
8 Correct 150 ms 32052 KB Output is correct
9 Correct 161 ms 31980 KB Output is correct
10 Correct 149 ms 32332 KB Output is correct
11 Correct 146 ms 32308 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12116 KB Output is correct
2 Correct 8 ms 12372 KB Output is correct
3 Correct 9 ms 12560 KB Output is correct
4 Correct 8 ms 12244 KB Output is correct
5 Correct 8 ms 12408 KB Output is correct
6 Correct 9 ms 12252 KB Output is correct
7 Correct 9 ms 12184 KB Output is correct
8 Correct 108 ms 18132 KB Output is correct
9 Correct 103 ms 17996 KB Output is correct
10 Correct 106 ms 18412 KB Output is correct
11 Correct 106 ms 18880 KB Output is correct
12 Correct 99 ms 17644 KB Output is correct
13 Correct 101 ms 18188 KB Output is correct
14 Correct 106 ms 18196 KB Output is correct
15 Correct 107 ms 18212 KB Output is correct
16 Correct 96 ms 18136 KB Output is correct
17 Correct 106 ms 18124 KB Output is correct
18 Correct 112 ms 18192 KB Output is correct
19 Correct 107 ms 18288 KB Output is correct
20 Correct 98 ms 18408 KB Output is correct
21 Correct 101 ms 18128 KB Output is correct
22 Correct 106 ms 18220 KB Output is correct
23 Correct 111 ms 18124 KB Output is correct
24 Correct 101 ms 18096 KB Output is correct
25 Correct 102 ms 17996 KB Output is correct
26 Correct 101 ms 17956 KB Output is correct
27 Correct 183 ms 24224 KB Output is correct
28 Correct 186 ms 26508 KB Output is correct
29 Correct 186 ms 28472 KB Output is correct
30 Correct 181 ms 26116 KB Output is correct
31 Correct 178 ms 26328 KB Output is correct
32 Correct 159 ms 27448 KB Output is correct
33 Correct 153 ms 31828 KB Output is correct
34 Correct 150 ms 32052 KB Output is correct
35 Correct 161 ms 31980 KB Output is correct
36 Correct 149 ms 32332 KB Output is correct
37 Correct 146 ms 32308 KB Output is correct
38 Correct 276 ms 35200 KB Output is correct
39 Correct 295 ms 36908 KB Output is correct
40 Correct 241 ms 32476 KB Output is correct
41 Correct 316 ms 60400 KB Output is correct
42 Correct 155 ms 24516 KB Output is correct
43 Correct 178 ms 24548 KB Output is correct
44 Correct 224 ms 30912 KB Output is correct
45 Correct 221 ms 31180 KB Output is correct
46 Correct 229 ms 31524 KB Output is correct
47 Correct 157 ms 29360 KB Output is correct
48 Correct 153 ms 28920 KB Output is correct
49 Correct 224 ms 32408 KB Output is correct
50 Correct 214 ms 34400 KB Output is correct
51 Correct 237 ms 35692 KB Output is correct
52 Correct 175 ms 34140 KB Output is correct
53 Correct 219 ms 42276 KB Output is correct
54 Correct 231 ms 47164 KB Output is correct
55 Correct 212 ms 40772 KB Output is correct