oj.uz

Submission #1097589

# Submission time Handle Problem Language Result Execution time Memory
1097589 2024-10-07T15:23:59 Z peti1234 Long Mansion (JOI17_long_mansion) C++17
100 / 100
 763 ms 35112 KB 
#include <bits/stdc++.h>
using namespace std;

const int c=500005;
int n, q, t[c], ord[c], l[c], r[c], el[c], kov[c];
vector<int> sor[c];
int main() {
	ios_base::sync_with_stdio(false);
	cin >> n;
	for (int i=1; i<n; i++) {
		cin >> t[i];
	}
	for (int i=1; i<=n; i++) {
		int x;
		cin >> x;
		while (x--) {
			int y;
			cin >> y;
			sor[y].push_back(i);
		}
	}
	for (int i=1; i<n; i++) {
		int si=sor[t[i]].size();
		int lo=-1, hi=si, mid;
		while (hi-lo>1) {
			mid=(hi+lo)/2;
			if (sor[t[i]][mid]<=i) {
				lo=mid;
			} else {
				hi=mid;
			}
		}
		if (lo==-1) {
			el[i]=0;
		} else {
			el[i]=sor[t[i]][lo];
		}
		if (hi==si) {
			kov[i]=n+1;
		} else {
			kov[i]=sor[t[i]][hi];
		}
	}

	for (int i=1; i<=n; i++) {
		ord[i]=i;
	}
	random_shuffle(ord+1, ord+n+1);
	for (int i=1; i<=n; i++) {
		int bal=ord[i], jobb=ord[i];
		while (true) {
			int d=jobb-bal;
			if (l[bal]) {
				jobb=max(jobb, r[bal]);
				bal=min(bal, l[bal]);
			}
			if (r[jobb]) {
				bal=min(bal, l[jobb]);
				jobb=max(jobb, r[jobb]);
			}
			if (bal>1 && kov[bal-1]<=jobb) {
				bal--;
			}
			if (jobb<n && el[jobb]>=bal) {
				jobb++;
			}
			if (jobb-bal==d) {
				break;
			}
		}
		l[ord[i]]=bal, r[ord[i]]=jobb;
	}
	int q;
	cin >> q;
	while (q--) {
		int a, b;
		cin >> a >> b;
		cout << (l[a]<=b && b<=r[a] ? "YES" : "NO") << "\n";
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12124 KB Output is correct
2 Correct 12 ms 12300 KB Output is correct
3 Correct 11 ms 12380 KB Output is correct
4 Correct 11 ms 12348 KB Output is correct
5 Correct 11 ms 12124 KB Output is correct
6 Correct 11 ms 12224 KB Output is correct
7 Correct 11 ms 12364 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12124 KB Output is correct
2 Correct 12 ms 12300 KB Output is correct
3 Correct 11 ms 12380 KB Output is correct
4 Correct 11 ms 12348 KB Output is correct
5 Correct 11 ms 12124 KB Output is correct
6 Correct 11 ms 12224 KB Output is correct
7 Correct 11 ms 12364 KB Output is correct
8 Correct 594 ms 13648 KB Output is correct
9 Correct 609 ms 13652 KB Output is correct
10 Correct 576 ms 13908 KB Output is correct
11 Correct 583 ms 14016 KB Output is correct
12 Correct 575 ms 13904 KB Output is correct
13 Correct 578 ms 14028 KB Output is correct
14 Correct 583 ms 13908 KB Output is correct
15 Correct 574 ms 13908 KB Output is correct
16 Correct 569 ms 14180 KB Output is correct
17 Correct 594 ms 13904 KB Output is correct
18 Correct 612 ms 13916 KB Output is correct
19 Correct 591 ms 13908 KB Output is correct
20 Correct 626 ms 13988 KB Output is correct
21 Correct 598 ms 14092 KB Output is correct
22 Correct 578 ms 14064 KB Output is correct
23 Correct 592 ms 13928 KB Output is correct
24 Correct 597 ms 13908 KB Output is correct
25 Correct 583 ms 13904 KB Output is correct
26 Correct 634 ms 13740 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 620 ms 18400 KB Output is correct
2 Correct 632 ms 18056 KB Output is correct
3 Correct 643 ms 18048 KB Output is correct
4 Correct 624 ms 18280 KB Output is correct
5 Correct 674 ms 18560 KB Output is correct
6 Correct 612 ms 17532 KB Output is correct
7 Correct 621 ms 17492 KB Output is correct
8 Correct 653 ms 17756 KB Output is correct
9 Correct 615 ms 17644 KB Output is correct
10 Correct 622 ms 17704 KB Output is correct
11 Correct 763 ms 17708 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12124 KB Output is correct
2 Correct 12 ms 12300 KB Output is correct
3 Correct 11 ms 12380 KB Output is correct
4 Correct 11 ms 12348 KB Output is correct
5 Correct 11 ms 12124 KB Output is correct
6 Correct 11 ms 12224 KB Output is correct
7 Correct 11 ms 12364 KB Output is correct
8 Correct 594 ms 13648 KB Output is correct
9 Correct 609 ms 13652 KB Output is correct
10 Correct 576 ms 13908 KB Output is correct
11 Correct 583 ms 14016 KB Output is correct
12 Correct 575 ms 13904 KB Output is correct
13 Correct 578 ms 14028 KB Output is correct
14 Correct 583 ms 13908 KB Output is correct
15 Correct 574 ms 13908 KB Output is correct
16 Correct 569 ms 14180 KB Output is correct
17 Correct 594 ms 13904 KB Output is correct
18 Correct 612 ms 13916 KB Output is correct
19 Correct 591 ms 13908 KB Output is correct
20 Correct 626 ms 13988 KB Output is correct
21 Correct 598 ms 14092 KB Output is correct
22 Correct 578 ms 14064 KB Output is correct
23 Correct 592 ms 13928 KB Output is correct
24 Correct 597 ms 13908 KB Output is correct
25 Correct 583 ms 13904 KB Output is correct
26 Correct 634 ms 13740 KB Output is correct
27 Correct 620 ms 18400 KB Output is correct
28 Correct 632 ms 18056 KB Output is correct
29 Correct 643 ms 18048 KB Output is correct
30 Correct 624 ms 18280 KB Output is correct
31 Correct 674 ms 18560 KB Output is correct
32 Correct 612 ms 17532 KB Output is correct
33 Correct 621 ms 17492 KB Output is correct
34 Correct 653 ms 17756 KB Output is correct
35 Correct 615 ms 17644 KB Output is correct
36 Correct 622 ms 17704 KB Output is correct
37 Correct 763 ms 17708 KB Output is correct
38 Correct 739 ms 25936 KB Output is correct
39 Correct 754 ms 28316 KB Output is correct
40 Correct 710 ms 23888 KB Output is correct
41 Correct 732 ms 27716 KB Output is correct
42 Correct 654 ms 17748 KB Output is correct
43 Correct 680 ms 17616 KB Output is correct
44 Correct 718 ms 21980 KB Output is correct
45 Correct 674 ms 22176 KB Output is correct
46 Correct 700 ms 22608 KB Output is correct
47 Correct 619 ms 18120 KB Output is correct
48 Correct 701 ms 17816 KB Output is correct
49 Correct 756 ms 21536 KB Output is correct
50 Correct 667 ms 21888 KB Output is correct
51 Correct 760 ms 22892 KB Output is correct
52 Correct 643 ms 24408 KB Output is correct
53 Correct 677 ms 29388 KB Output is correct
54 Correct 750 ms 35112 KB Output is correct
55 Correct 668 ms 29528 KB Output is correct