답안 #294539

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
294539	2020-09-09T04:13:06 Z	nandonathaniel	Long Mansion (JOI17_long_mansion)	C++14	100 / 100	303 ms	52344 KB

long_mansion

#include<bits/stdc++.h>
using namespace std;
const int MAXN=500005;

int C[MAXN],kiri[MAXN],kanan[MAXN],nearL[MAXN],nearR[MAXN],last[MAXN];
vector<int> kunci[MAXN];

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int n,q,b,a;
	cin >> n;
	for(int i=1;i<n;i++)cin >> C[i];
	for(int i=1;i<=n;i++){
		cin >> b;
		for(int j=1;j<=b;j++){
			cin >> a;
			kunci[i].push_back(a);
		}
	}
	for(int i=1;i<n;i++){
		for(auto isi : kunci[i]){
			last[isi]=i;
		}
		nearL[i]=last[C[i]];
	}
	for(int i=1;i<=n;i++)last[i]=n+5;
	for(int i=n-1;i>=1;i--){
		for(auto isi : kunci[i+1]){
			last[isi]=i+1;
		}
		nearR[i]=last[C[i]];
	}
	for(int i=1;i<=n;i++){
		kiri[i]=i;kanan[i]=i;
		while(true){
			if(kiri[i]-1>=1 && nearR[kiri[i]-1]<=kanan[i]){
				kanan[i]=max(kanan[i],kanan[kiri[i]-1]);
				kiri[i]=kiri[kiri[i]-1];
			}
			else if(kanan[i]+1<=n && nearL[kanan[i]]>=kiri[i]){
				kanan[i]++;
			}
			else break;
		}
	}
	cin >> q;
	while(q--){
		cin >> a >> b;
		if(b>a){
			if(b<=kanan[a])cout << "YES\n";
			else cout << "NO\n";
		}
		else{
			if(b>=kiri[a])cout << "YES\n";
			else cout << "NO\n";
		}
	}
	return 0;
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	12392 KB	Output is correct
2	Correct	10 ms	12416 KB	Output is correct
3	Correct	10 ms	12544 KB	Output is correct
4	Correct	10 ms	12288 KB	Output is correct
5	Correct	10 ms	12288 KB	Output is correct
6	Correct	10 ms	12288 KB	Output is correct
7	Correct	10 ms	12320 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	12392 KB	Output is correct
2	Correct	10 ms	12416 KB	Output is correct
3	Correct	10 ms	12544 KB	Output is correct
4	Correct	10 ms	12288 KB	Output is correct
5	Correct	10 ms	12288 KB	Output is correct
6	Correct	10 ms	12288 KB	Output is correct
7	Correct	10 ms	12320 KB	Output is correct
8	Correct	116 ms	18168 KB	Output is correct
9	Correct	112 ms	18116 KB	Output is correct
10	Correct	116 ms	18588 KB	Output is correct
11	Correct	120 ms	18936 KB	Output is correct
12	Correct	107 ms	17784 KB	Output is correct
13	Correct	115 ms	18296 KB	Output is correct
14	Correct	113 ms	18464 KB	Output is correct
15	Correct	112 ms	18296 KB	Output is correct
16	Correct	107 ms	18296 KB	Output is correct
17	Correct	116 ms	18296 KB	Output is correct
18	Correct	116 ms	18424 KB	Output is correct
19	Correct	118 ms	18424 KB	Output is correct
20	Correct	109 ms	18296 KB	Output is correct
21	Correct	110 ms	18168 KB	Output is correct
22	Correct	118 ms	18296 KB	Output is correct
23	Correct	116 ms	18168 KB	Output is correct
24	Correct	112 ms	18168 KB	Output is correct
25	Correct	115 ms	18168 KB	Output is correct
26	Correct	112 ms	18168 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	197 ms	27256 KB	Output is correct
2	Correct	192 ms	27128 KB	Output is correct
3	Correct	189 ms	27000 KB	Output is correct
4	Correct	196 ms	27128 KB	Output is correct
5	Correct	192 ms	27128 KB	Output is correct
6	Correct	166 ms	25848 KB	Output is correct
7	Correct	164 ms	25720 KB	Output is correct
8	Correct	163 ms	25592 KB	Output is correct
9	Correct	175 ms	25704 KB	Output is correct
10	Correct	158 ms	25592 KB	Output is correct
11	Correct	161 ms	25592 KB	Output is correct

Subtask #4
75.0 / 75.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	12392 KB	Output is correct
2	Correct	10 ms	12416 KB	Output is correct
3	Correct	10 ms	12544 KB	Output is correct
4	Correct	10 ms	12288 KB	Output is correct
5	Correct	10 ms	12288 KB	Output is correct
6	Correct	10 ms	12288 KB	Output is correct
7	Correct	10 ms	12320 KB	Output is correct
8	Correct	116 ms	18168 KB	Output is correct
9	Correct	112 ms	18116 KB	Output is correct
10	Correct	116 ms	18588 KB	Output is correct
11	Correct	120 ms	18936 KB	Output is correct
12	Correct	107 ms	17784 KB	Output is correct
13	Correct	115 ms	18296 KB	Output is correct
14	Correct	113 ms	18464 KB	Output is correct
15	Correct	112 ms	18296 KB	Output is correct
16	Correct	107 ms	18296 KB	Output is correct
17	Correct	116 ms	18296 KB	Output is correct
18	Correct	116 ms	18424 KB	Output is correct
19	Correct	118 ms	18424 KB	Output is correct
20	Correct	109 ms	18296 KB	Output is correct
21	Correct	110 ms	18168 KB	Output is correct
22	Correct	118 ms	18296 KB	Output is correct
23	Correct	116 ms	18168 KB	Output is correct
24	Correct	112 ms	18168 KB	Output is correct
25	Correct	115 ms	18168 KB	Output is correct
26	Correct	112 ms	18168 KB	Output is correct
27	Correct	197 ms	27256 KB	Output is correct
28	Correct	192 ms	27128 KB	Output is correct
29	Correct	189 ms	27000 KB	Output is correct
30	Correct	196 ms	27128 KB	Output is correct
31	Correct	192 ms	27128 KB	Output is correct
32	Correct	166 ms	25848 KB	Output is correct
33	Correct	164 ms	25720 KB	Output is correct
34	Correct	163 ms	25592 KB	Output is correct
35	Correct	175 ms	25704 KB	Output is correct
36	Correct	158 ms	25592 KB	Output is correct
37	Correct	161 ms	25592 KB	Output is correct
38	Correct	287 ms	47224 KB	Output is correct
39	Correct	293 ms	52344 KB	Output is correct
40	Correct	268 ms	40568 KB	Output is correct
41	Correct	303 ms	50808 KB	Output is correct
42	Correct	172 ms	26744 KB	Output is correct
43	Correct	175 ms	26872 KB	Output is correct
44	Correct	233 ms	34936 KB	Output is correct
45	Correct	235 ms	35192 KB	Output is correct
46	Correct	235 ms	35196 KB	Output is correct
47	Correct	171 ms	27128 KB	Output is correct
48	Correct	172 ms	26620 KB	Output is correct
49	Correct	235 ms	34936 KB	Output is correct
50	Correct	231 ms	35064 KB	Output is correct
51	Correct	247 ms	35320 KB	Output is correct
52	Correct	206 ms	33864 KB	Output is correct
53	Correct	243 ms	41080 KB	Output is correct
54	Correct	288 ms	48120 KB	Output is correct
55	Correct	245 ms	41208 KB	Output is correct

답안 #294539

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 5.0 / 5.0

Subtask #3 15.0 / 15.0

Subtask #4 75.0 / 75.0

Subtask #1
5.0 / 5.0

Subtask #2
5.0 / 5.0

Subtask #3
15.0 / 15.0

Subtask #4
75.0 / 75.0