oj.uz

Submission #131097

# Submission time Handle Problem Language Result Execution time Memory
131097 2019-07-16T12:56:28 Z baluteshih Long Mansion (JOI17_long_mansion) C++14
100 / 100
 380 ms 44348 KB 
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define ET cout << "\n"
#define ALL(v) v.begin(),v.end()
#define MP make_pair
#define F first
#define S second
#define MEM(i,j) memset(i,j,sizeof i)
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

vector<int> v[500005];
int L[500005],R[500005],key[500005],ls[500005];
int rm[500005],relL[500005],relR[500005];

int main()
{jizz
	int n,c,x,q,l,r;
	cin >> n;
	for(int i=1;i<n;++i)
		cin >> key[i];
	for(int i=1;i<=n;++i)
		for(cin >> c,v[i].resize(c);c--;)
			cin >> x,v[i][c]=x;
	for(int i=1;i<n;L[i]=ls[key[i]],++i)
		for(int j:v[i])
			ls[j]=i;
	fill(ls+1,ls+n+1,n+1),R[0]=n+1;
	for(int i=n-1;i>0;R[i]=ls[key[i]],--i)
		for(int j:v[i+1])
			ls[j]=i+1;
	for(int i=n;i>0;--i)
		for(rm[i]=i;L[rm[i]]>=i;rm[i]=rm[rm[i]+1]);
	for(int i=1;i<=n;++i)
		if(R[i-1]>rm[i])
			relL[i]=i,relR[i]=rm[i];
		else
			for(relL[i]=relL[i-1],relR[i]=max(rm[i],relR[i-1]);L[relR[i]]>=relL[i]||R[relL[i]-1]<=relR[i];)
				if(L[relR[i]]>=relL[i])
					relR[i]=rm[relR[i]+1];
				else if(R[relL[i]-1]<=relR[i])
					relL[i]=relL[relL[i]-1],relR[i]=max(relR[i],relR[relL[i]]);
	for(cin >> q;q--;)
		if(cin >> l >> r,relL[l]<=r&&relR[l]>=r)
			cout << "YES\n";
		else
			cout << "NO\n";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12280 KB Output is correct
2 Correct 16 ms 12392 KB Output is correct
3 Correct 17 ms 12536 KB Output is correct
4 Correct 16 ms 12280 KB Output is correct
5 Correct 16 ms 12280 KB Output is correct
6 Correct 16 ms 12280 KB Output is correct
7 Correct 16 ms 12280 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12280 KB Output is correct
2 Correct 16 ms 12392 KB Output is correct
3 Correct 17 ms 12536 KB Output is correct
4 Correct 16 ms 12280 KB Output is correct
5 Correct 16 ms 12280 KB Output is correct
6 Correct 16 ms 12280 KB Output is correct
7 Correct 16 ms 12280 KB Output is correct
8 Correct 131 ms 15160 KB Output is correct
9 Correct 134 ms 15124 KB Output is correct
10 Correct 135 ms 15332 KB Output is correct
11 Correct 133 ms 15608 KB Output is correct
12 Correct 122 ms 15292 KB Output is correct
13 Correct 133 ms 15376 KB Output is correct
14 Correct 129 ms 15352 KB Output is correct
15 Correct 127 ms 15480 KB Output is correct
16 Correct 127 ms 15608 KB Output is correct
17 Correct 129 ms 15344 KB Output is correct
18 Correct 131 ms 15352 KB Output is correct
19 Correct 127 ms 15408 KB Output is correct
20 Correct 135 ms 15620 KB Output is correct
21 Correct 127 ms 15688 KB Output is correct
22 Correct 137 ms 15424 KB Output is correct
23 Correct 128 ms 15192 KB Output is correct
24 Correct 128 ms 15224 KB Output is correct
25 Correct 128 ms 15296 KB Output is correct
26 Correct 130 ms 15240 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 20816 KB Output is correct
2 Correct 214 ms 21112 KB Output is correct
3 Correct 209 ms 21116 KB Output is correct
4 Correct 216 ms 21080 KB Output is correct
5 Correct 219 ms 21148 KB Output is correct
6 Correct 190 ms 21328 KB Output is correct
7 Correct 194 ms 21380 KB Output is correct
8 Correct 190 ms 21360 KB Output is correct
9 Correct 196 ms 21368 KB Output is correct
10 Correct 193 ms 21456 KB Output is correct
11 Correct 190 ms 21492 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12280 KB Output is correct
2 Correct 16 ms 12392 KB Output is correct
3 Correct 17 ms 12536 KB Output is correct
4 Correct 16 ms 12280 KB Output is correct
5 Correct 16 ms 12280 KB Output is correct
6 Correct 16 ms 12280 KB Output is correct
7 Correct 16 ms 12280 KB Output is correct
8 Correct 131 ms 15160 KB Output is correct
9 Correct 134 ms 15124 KB Output is correct
10 Correct 135 ms 15332 KB Output is correct
11 Correct 133 ms 15608 KB Output is correct
12 Correct 122 ms 15292 KB Output is correct
13 Correct 133 ms 15376 KB Output is correct
14 Correct 129 ms 15352 KB Output is correct
15 Correct 127 ms 15480 KB Output is correct
16 Correct 127 ms 15608 KB Output is correct
17 Correct 129 ms 15344 KB Output is correct
18 Correct 131 ms 15352 KB Output is correct
19 Correct 127 ms 15408 KB Output is correct
20 Correct 135 ms 15620 KB Output is correct
21 Correct 127 ms 15688 KB Output is correct
22 Correct 137 ms 15424 KB Output is correct
23 Correct 128 ms 15192 KB Output is correct
24 Correct 128 ms 15224 KB Output is correct
25 Correct 128 ms 15296 KB Output is correct
26 Correct 130 ms 15240 KB Output is correct
27 Correct 228 ms 20816 KB Output is correct
28 Correct 214 ms 21112 KB Output is correct
29 Correct 209 ms 21116 KB Output is correct
30 Correct 216 ms 21080 KB Output is correct
31 Correct 219 ms 21148 KB Output is correct
32 Correct 190 ms 21328 KB Output is correct
33 Correct 194 ms 21380 KB Output is correct
34 Correct 190 ms 21360 KB Output is correct
35 Correct 196 ms 21368 KB Output is correct
36 Correct 193 ms 21456 KB Output is correct
37 Correct 190 ms 21492 KB Output is correct
38 Correct 348 ms 38192 KB Output is correct
39 Correct 363 ms 44020 KB Output is correct
40 Correct 344 ms 32480 KB Output is correct
41 Correct 359 ms 44348 KB Output is correct
42 Correct 200 ms 20916 KB Output is correct
43 Correct 198 ms 20856 KB Output is correct
44 Correct 270 ms 26804 KB Output is correct
45 Correct 276 ms 26684 KB Output is correct
46 Correct 276 ms 26688 KB Output is correct
47 Correct 202 ms 20864 KB Output is correct
48 Correct 198 ms 20864 KB Output is correct
49 Correct 278 ms 26748 KB Output is correct
50 Correct 268 ms 26616 KB Output is correct
51 Correct 278 ms 26472 KB Output is correct
52 Correct 259 ms 26352 KB Output is correct
53 Correct 310 ms 32272 KB Output is correct
54 Correct 380 ms 37860 KB Output is correct
55 Correct 364 ms 32028 KB Output is correct