oj.uz

Submission #511259

# Submission time Handle Problem Language Result Execution time Memory
511259 2022-01-15T13:08:55 Z ArianKheirandish Long Mansion (JOI17_long_mansion) C++17
100 / 100
 316 ms 68956 KB 
// in the name of God//
 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x)    cerr << #x << " = " << x << endl;
const int maxn = 5e5 + 10;
int n, q;
vector<int> a[maxn], keys[maxn];
int b[maxn], c[maxn];
int dpL[maxn], dpR[maxn];

bool check(int l, int r, int x){
	int ind = lower_bound(keys[x].begin(),keys[x].end(), l) - keys[x].begin();
	if(ind < keys[x].size() && keys[x][ind] <= r)
		return 1;
	else
		return 0;
}

int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin >> n;
	for(int i = 1 ; i < n ; i ++)
		cin >> c[i];
		
	for(int i = 1 ; i <= n ; i ++){
		cin >> b[i];
		for(int j = 0 ; j < b[i] ; j ++){
			int x;
			cin >> x;
			a[i].push_back(x);
		}
		for(auto x : a[i])
			keys[x].push_back(i);
	}
	
	for(int i = 1 ; i <= n ; i ++)
		dpL[i] = dpR[i] = i;
		
	for(int i = 1 ; i <= n ; i ++){
		while(1){
			if(dpL[i] > 1 && check(dpL[i], dpR[i], c[dpL[i] - 1]))
				dpR[i] = max(dpR[i], dpR[dpL[i] - 1]),
				dpL[i] = dpL[dpL[i] - 1];
		
			else if(dpR[i] < n && check(dpL[i], dpR[i], c[dpR[i]]))
				dpR[i] = dpR[i] + 1;
			
			else
				break;
		}
		
		//debug(i);
	}
	
	cin >> q;
	while(q --){
		int x, y;
		cin >> x >> y;
		cout << ((dpL[x] <= y && y <= dpR[x]) ? "YES" : "NO") << '\n';
	}
	return 0;
}

Compilation message

long_mansion.cpp: In function 'bool check(int, int, int)':
long_mansion.cpp:15:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |  if(ind < keys[x].size() && keys[x][ind] <= r)
      |     ~~~~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23884 KB Output is correct
2 Correct 14 ms 24012 KB Output is correct
3 Correct 14 ms 24100 KB Output is correct
4 Correct 13 ms 23888 KB Output is correct
5 Correct 14 ms 23980 KB Output is correct
6 Correct 13 ms 23884 KB Output is correct
7 Correct 13 ms 23896 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23884 KB Output is correct
2 Correct 14 ms 24012 KB Output is correct
3 Correct 14 ms 24100 KB Output is correct
4 Correct 13 ms 23888 KB Output is correct
5 Correct 14 ms 23980 KB Output is correct
6 Correct 13 ms 23884 KB Output is correct
7 Correct 13 ms 23896 KB Output is correct
8 Correct 100 ms 25476 KB Output is correct
9 Correct 106 ms 25356 KB Output is correct
10 Correct 100 ms 25676 KB Output is correct
11 Correct 107 ms 25796 KB Output is correct
12 Correct 102 ms 25644 KB Output is correct
13 Correct 94 ms 25668 KB Output is correct
14 Correct 101 ms 25592 KB Output is correct
15 Correct 99 ms 25668 KB Output is correct
16 Correct 112 ms 25896 KB Output is correct
17 Correct 101 ms 25560 KB Output is correct
18 Correct 99 ms 25684 KB Output is correct
19 Correct 99 ms 25792 KB Output is correct
20 Correct 112 ms 25900 KB Output is correct
21 Correct 96 ms 25876 KB Output is correct
22 Correct 104 ms 25676 KB Output is correct
23 Correct 99 ms 25512 KB Output is correct
24 Correct 109 ms 25512 KB Output is correct
25 Correct 105 ms 25456 KB Output is correct
26 Correct 103 ms 25508 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 38372 KB Output is correct
2 Correct 183 ms 39644 KB Output is correct
3 Correct 175 ms 39456 KB Output is correct
4 Correct 188 ms 39992 KB Output is correct
5 Correct 208 ms 40096 KB Output is correct
6 Correct 164 ms 37684 KB Output is correct
7 Correct 153 ms 37436 KB Output is correct
8 Correct 149 ms 37496 KB Output is correct
9 Correct 147 ms 37552 KB Output is correct
10 Correct 152 ms 37408 KB Output is correct
11 Correct 150 ms 37400 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23884 KB Output is correct
2 Correct 14 ms 24012 KB Output is correct
3 Correct 14 ms 24100 KB Output is correct
4 Correct 13 ms 23888 KB Output is correct
5 Correct 14 ms 23980 KB Output is correct
6 Correct 13 ms 23884 KB Output is correct
7 Correct 13 ms 23896 KB Output is correct
8 Correct 100 ms 25476 KB Output is correct
9 Correct 106 ms 25356 KB Output is correct
10 Correct 100 ms 25676 KB Output is correct
11 Correct 107 ms 25796 KB Output is correct
12 Correct 102 ms 25644 KB Output is correct
13 Correct 94 ms 25668 KB Output is correct
14 Correct 101 ms 25592 KB Output is correct
15 Correct 99 ms 25668 KB Output is correct
16 Correct 112 ms 25896 KB Output is correct
17 Correct 101 ms 25560 KB Output is correct
18 Correct 99 ms 25684 KB Output is correct
19 Correct 99 ms 25792 KB Output is correct
20 Correct 112 ms 25900 KB Output is correct
21 Correct 96 ms 25876 KB Output is correct
22 Correct 104 ms 25676 KB Output is correct
23 Correct 99 ms 25512 KB Output is correct
24 Correct 109 ms 25512 KB Output is correct
25 Correct 105 ms 25456 KB Output is correct
26 Correct 103 ms 25508 KB Output is correct
27 Correct 188 ms 38372 KB Output is correct
28 Correct 183 ms 39644 KB Output is correct
29 Correct 175 ms 39456 KB Output is correct
30 Correct 188 ms 39992 KB Output is correct
31 Correct 208 ms 40096 KB Output is correct
32 Correct 164 ms 37684 KB Output is correct
33 Correct 153 ms 37436 KB Output is correct
34 Correct 149 ms 37496 KB Output is correct
35 Correct 147 ms 37552 KB Output is correct
36 Correct 152 ms 37408 KB Output is correct
37 Correct 150 ms 37400 KB Output is correct
38 Correct 285 ms 58708 KB Output is correct
39 Correct 276 ms 62796 KB Output is correct
40 Correct 255 ms 52752 KB Output is correct
41 Correct 307 ms 60520 KB Output is correct
42 Correct 166 ms 39192 KB Output is correct
43 Correct 171 ms 39148 KB Output is correct
44 Correct 267 ms 48392 KB Output is correct
45 Correct 252 ms 48704 KB Output is correct
46 Correct 266 ms 49172 KB Output is correct
47 Correct 166 ms 39428 KB Output is correct
48 Correct 171 ms 38776 KB Output is correct
49 Correct 263 ms 47676 KB Output is correct
50 Correct 269 ms 48180 KB Output is correct
51 Correct 265 ms 49648 KB Output is correct
52 Correct 190 ms 49864 KB Output is correct
53 Correct 251 ms 59084 KB Output is correct
54 Correct 316 ms 68956 KB Output is correct
55 Correct 254 ms 59316 KB Output is correct