oj.uz

Submission #984333

# Submission time Handle Problem Language Result Execution time Memory
984333 2024-05-16T14:02:41 Z AmirAli_H1 Long Mansion (JOI17_long_mansion) C++17
10 / 100
 3000 ms 50720 KB 
// In the name of Allah

#include <bits/stdc++.h>
using namespace std;

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		X						real()
#define		Y						imag()
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);

int n, q;
const int maxn = 5e5 + 7;
int A[maxn]; vector<int> ls[maxn];
int A1[maxn], A2[maxn], ind[maxn];
vector<int> lsx[maxn]; set<int> st;
int val1[maxn], val2[maxn];

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	cin >> n;
	for (int i = 1; i <= n - 1; i++) {
		cin >> A[i]; A[i]--;
	}
	for (int i = 1; i <= n; i++) {
		int T;
		cin >> T;
		while (T--) {
			int x;
			cin >> x; x--;
			ls[i].pb(x);
		}
	}
	
	fill(ind, ind + n, 0);
	for (int i = 1; i <= n; i++) {
		for (int j : ls[i]) ind[j] = i;
		if (i <= n - 1) A1[i] = ind[A[i]];
	}
	
	fill(ind, ind + n, n + 1);
	for (int i = n; i >= 1; i--) {
		for (int j : ls[i]) ind[j] = i;
		if (i - 1 >= 1) A2[i - 1] = ind[A[i - 1]];
	}
	
	st.clear();
	for (int i = 0; i <= n + 1; i++) lsx[i].clear();
	for (int i = 1; i <= n - 1; i++) lsx[A2[i]].pb(i);
	for (int i = n + 1; i >= 0; i--) {
		for (int j : lsx[i]) st.insert(j);
		if (i - 1 >= 1 && i - 1 <= n - 1) {
			if (A1[i - 1] == 0) val1[i - 1] = 0;
			else {
				auto it = st.lower_bound(A1[i - 1]);
				if (it == st.end()) val1[i - 1] = n + 1;
				else val1[i - 1] = (*it) + 1;
			}
		}
	}
	
	st.clear();
	for (int i = 0; i <= n + 1; i++) lsx[i].clear();
	for (int i = 1; i <= n - 1; i++) lsx[A1[i]].pb(i);
	for (int i = 0; i <= n + 1; i++) {
		for (int j : lsx[i]) st.insert(j);
		if (i >= 1 && i <= n - 1) {
			if (A2[i] == n + 1) val2[i + 1] = n + 1;
			else {
				auto it = st.lower_bound(A2[i]);
				if (it == st.begin()) val2[i + 1] = 0;
				else {
					it--; val2[i + 1] = *it;
				}
			}
		}
	}
	
	cin >> q;
	while (q--) {
		int u, v;
		cin >> u >> v;
		
		bool flag = 1;
		if (u < v) {
			for (int i = u; i < v; i++) {
				if (val1[i] <= u) flag = 0;
			}
		}
		else {
			for (int i = u; i > v; i--) {
				if (val2[i] >= u) flag = 0;
			}
		}
		
		if (flag) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 35416 KB Output is correct
2 Correct 12 ms 35676 KB Output is correct
3 Correct 15 ms 35932 KB Output is correct
4 Correct 9 ms 35508 KB Output is correct
5 Correct 14 ms 35632 KB Output is correct
6 Correct 9 ms 35676 KB Output is correct
7 Correct 9 ms 35420 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 35416 KB Output is correct
2 Correct 12 ms 35676 KB Output is correct
3 Correct 15 ms 35932 KB Output is correct
4 Correct 9 ms 35508 KB Output is correct
5 Correct 14 ms 35632 KB Output is correct
6 Correct 9 ms 35676 KB Output is correct
7 Correct 9 ms 35420 KB Output is correct
8 Correct 275 ms 41364 KB Output is correct
9 Correct 277 ms 41412 KB Output is correct
10 Correct 366 ms 41812 KB Output is correct
11 Correct 568 ms 42184 KB Output is correct
12 Correct 184 ms 40784 KB Output is correct
13 Correct 99 ms 41556 KB Output is correct
14 Correct 98 ms 41660 KB Output is correct
15 Correct 175 ms 41804 KB Output is correct
16 Correct 371 ms 41304 KB Output is correct
17 Correct 111 ms 41552 KB Output is correct
18 Correct 102 ms 41752 KB Output is correct
19 Correct 120 ms 41556 KB Output is correct
20 Correct 262 ms 41552 KB Output is correct
21 Correct 367 ms 41300 KB Output is correct
22 Correct 209 ms 41552 KB Output is correct
23 Correct 150 ms 41388 KB Output is correct
24 Correct 141 ms 41272 KB Output is correct
25 Correct 139 ms 41300 KB Output is correct
26 Correct 109 ms 41300 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3048 ms 50720 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 35416 KB Output is correct
2 Correct 12 ms 35676 KB Output is correct
3 Correct 15 ms 35932 KB Output is correct
4 Correct 9 ms 35508 KB Output is correct
5 Correct 14 ms 35632 KB Output is correct
6 Correct 9 ms 35676 KB Output is correct
7 Correct 9 ms 35420 KB Output is correct
8 Correct 275 ms 41364 KB Output is correct
9 Correct 277 ms 41412 KB Output is correct
10 Correct 366 ms 41812 KB Output is correct
11 Correct 568 ms 42184 KB Output is correct
12 Correct 184 ms 40784 KB Output is correct
13 Correct 99 ms 41556 KB Output is correct
14 Correct 98 ms 41660 KB Output is correct
15 Correct 175 ms 41804 KB Output is correct
16 Correct 371 ms 41304 KB Output is correct
17 Correct 111 ms 41552 KB Output is correct
18 Correct 102 ms 41752 KB Output is correct
19 Correct 120 ms 41556 KB Output is correct
20 Correct 262 ms 41552 KB Output is correct
21 Correct 367 ms 41300 KB Output is correct
22 Correct 209 ms 41552 KB Output is correct
23 Correct 150 ms 41388 KB Output is correct
24 Correct 141 ms 41272 KB Output is correct
25 Correct 139 ms 41300 KB Output is correct
26 Correct 109 ms 41300 KB Output is correct
27 Execution timed out 3048 ms 50720 KB Time limit exceeded
28 Halted 0 ms 0 KB -