oj.uz

Submission #697097

# Submission time Handle Problem Language Result Execution time Memory
697097 2023-02-08T09:53:15 Z amunduzbaev Long Mansion (JOI17_long_mansion) C++17
25 / 100
 3000 ms 52484 KB 
#include "bits/stdc++.h"
using namespace std;

#define ar array
typedef long long ll;
#define int ll

const int N = 5e5 + 5;
int c[N], b[N], last[N];
vector<int> a[N];
int l[N], r[N];
int L[N], R[N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin >> n;
	for(int i=1;i<n;i++){
		cin >> c[i];
	}
	
	for(int i=1;i<=n;i++){
		cin >> b[i];
		L[i] = 1, R[i] = n;
		a[i].resize(b[i]);
		for(int j=0;j<b[i];j++){
			cin >> a[i][j];
		}
	}
	
	for(int i=0;i<N;i++) last[i] = 0;
	for(int i=1;i<=n;i++){
		for(auto x : a[i]){
			last[x] = i;
		}
		l[i] = last[c[i]];
	}
	for(int i=0;i<N;i++) last[i] = n + 1;
	for(int i=n;i>0;i--){
		r[i] = last[c[i]];
		for(auto x : a[i]){
			last[x] = i;
		}
	}
	r[0] = N, l[n] = 0;
	for(int i=1;i<n;i++){
		int j = r[i] - 1;
		for(;i < j;j--){
			if(l[j] <= i){
				break;
			}
		}
		
		if(i < j && l[j] <= i){
			for(int k=i+1;k<=j;k++){
				L[k] = max(L[k], i + 1);
			}
		}
		
		j = l[i];
		for(;j < i;j++){
			if(i < r[j]){
				break;
			}
		}
		
		if(j < i && i < r[j]){
			for(int k=j+1;k<=i;k++){
				R[k] = min(R[k], i);
			}
		}
	}
	
	//~ for(int i=1;i<=n;i++){
		//~ cout<<L[i]<<" ";
	//~ } cout<<"\n";
	//~ for(int i=1;i<=n;i++){
		//~ cout<<R[i]<<" ";
	//~ } cout<<"\n";
	
	int q; cin >> q;
	while(q--){
		int a, b; cin >> a >> b;
		if(L[a] <= b && b <= R[a]){
			cout<<"YES\n";
		} else {
			cout<<"NO\n";
		}
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 16212 KB Output is correct
2 Correct 10 ms 16276 KB Output is correct
3 Correct 10 ms 16440 KB Output is correct
4 Correct 9 ms 16212 KB Output is correct
5 Correct 10 ms 16212 KB Output is correct
6 Correct 9 ms 16212 KB Output is correct
7 Correct 12 ms 16268 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 16212 KB Output is correct
2 Correct 10 ms 16276 KB Output is correct
3 Correct 10 ms 16440 KB Output is correct
4 Correct 9 ms 16212 KB Output is correct
5 Correct 10 ms 16212 KB Output is correct
6 Correct 9 ms 16212 KB Output is correct
7 Correct 12 ms 16268 KB Output is correct
8 Correct 97 ms 22092 KB Output is correct
9 Correct 93 ms 22008 KB Output is correct
10 Correct 97 ms 22516 KB Output is correct
11 Correct 89 ms 22848 KB Output is correct
12 Correct 83 ms 21608 KB Output is correct
13 Correct 91 ms 22316 KB Output is correct
14 Correct 88 ms 22220 KB Output is correct
15 Correct 84 ms 22196 KB Output is correct
16 Correct 87 ms 22092 KB Output is correct
17 Correct 86 ms 22200 KB Output is correct
18 Correct 84 ms 22196 KB Output is correct
19 Correct 97 ms 22300 KB Output is correct
20 Correct 90 ms 22208 KB Output is correct
21 Correct 84 ms 22072 KB Output is correct
22 Correct 84 ms 22060 KB Output is correct
23 Correct 92 ms 22064 KB Output is correct
24 Correct 95 ms 21984 KB Output is correct
25 Correct 97 ms 22036 KB Output is correct
26 Correct 88 ms 22048 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 34264 KB Output is correct
2 Correct 140 ms 34056 KB Output is correct
3 Correct 143 ms 33772 KB Output is correct
4 Correct 160 ms 34124 KB Output is correct
5 Correct 156 ms 34252 KB Output is correct
6 Correct 127 ms 32124 KB Output is correct
7 Correct 124 ms 31860 KB Output is correct
8 Correct 131 ms 31760 KB Output is correct
9 Correct 128 ms 31840 KB Output is correct
10 Correct 130 ms 31864 KB Output is correct
11 Correct 122 ms 31820 KB Output is correct

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 16212 KB Output is correct
2 Correct 10 ms 16276 KB Output is correct
3 Correct 10 ms 16440 KB Output is correct
4 Correct 9 ms 16212 KB Output is correct
5 Correct 10 ms 16212 KB Output is correct
6 Correct 9 ms 16212 KB Output is correct
7 Correct 12 ms 16268 KB Output is correct
8 Correct 97 ms 22092 KB Output is correct
9 Correct 93 ms 22008 KB Output is correct
10 Correct 97 ms 22516 KB Output is correct
11 Correct 89 ms 22848 KB Output is correct
12 Correct 83 ms 21608 KB Output is correct
13 Correct 91 ms 22316 KB Output is correct
14 Correct 88 ms 22220 KB Output is correct
15 Correct 84 ms 22196 KB Output is correct
16 Correct 87 ms 22092 KB Output is correct
17 Correct 86 ms 22200 KB Output is correct
18 Correct 84 ms 22196 KB Output is correct
19 Correct 97 ms 22300 KB Output is correct
20 Correct 90 ms 22208 KB Output is correct
21 Correct 84 ms 22072 KB Output is correct
22 Correct 84 ms 22060 KB Output is correct
23 Correct 92 ms 22064 KB Output is correct
24 Correct 95 ms 21984 KB Output is correct
25 Correct 97 ms 22036 KB Output is correct
26 Correct 88 ms 22048 KB Output is correct
27 Correct 142 ms 34264 KB Output is correct
28 Correct 140 ms 34056 KB Output is correct
29 Correct 143 ms 33772 KB Output is correct
30 Correct 160 ms 34124 KB Output is correct
31 Correct 156 ms 34252 KB Output is correct
32 Correct 127 ms 32124 KB Output is correct
33 Correct 124 ms 31860 KB Output is correct
34 Correct 131 ms 31760 KB Output is correct
35 Correct 128 ms 31840 KB Output is correct
36 Correct 130 ms 31864 KB Output is correct
37 Correct 122 ms 31820 KB Output is correct
38 Execution timed out 3077 ms 52484 KB Time limit exceeded
39 Halted 0 ms 0 KB -