oj.uz

Submission #972060

# Submission time Handle Problem Language Result Execution time Memory
972060 2024-04-30T01:33:40 Z LCJLY Long Mansion (JOI17_long_mansion) C++14
100 / 100
 236 ms 48080 KB 
#include <bits/stdc++.h>
using namespace std;
	
#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<long long,long long>pii;
typedef pair<int,pii>pi2;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
 
vector<int>storage[500005];
 
bool f(int val, int l, int r){
	int index=lower_bound(storage[val].begin(),storage[val].end(),l)-storage[val].begin();
	//show3(val,val,l,l,r,r);
	//show(sz,storage[val].size());
	if(index==(int)storage[val].size()) return false;
	//show2(index,index,storage[val][index],storage[val][index]);
	if(storage[val][index]<=r) return true;
	return false;
}
 
void solve(){
	int n;
	cin >> n;
	int arr[n+1];
	for(int x=1;x<n;x++){
		cin >> arr[x];
	}
	
	int temp,temp2;
	for(int x=1;x<=n;x++){
		cin >> temp;
		for(int y=0;y<temp;y++){
			cin >> temp2;
			storage[temp2].push_back(x);
		}
	}
	
	pii ans[n+5];
	memset(ans,-1,sizeof(ans));
	for(int x=1;x<=n;x++){
		int l=x;
		int r=x;
		while(1){
			if(l!=1&&f(arr[l-1],l,r)){
				l--;
				if(ans[l].first!=-1){
					r=max(r,ans[l].second);
					l=min(l,ans[l].first);
				}
			}
			else if(r!=n&&f(arr[r],l,r)){
				r++;
			}
			else break;
		}
		ans[x]={l,r};
		//show2(l,l,r,r);
	}
	
	int q;
	cin >> q;
	for(int x=0;x<q;x++){
		cin >> temp >> temp2;
		if(ans[temp].first<=temp2&&ans[temp].second>=temp2){
			cout << "YES\n";
		}
		else cout << "NO\n";
	}
	
}
 
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//freopen("in.txt","r",stdin);
	//cin >> t;
	while(t--){
		solve();
	}
}

Compilation message

long_mansion.cpp: In function 'void solve()':
long_mansion.cpp:44:27: warning: 'void* memset(void*, int, size_t)' writing to an object of type 'pii' {aka 'struct std::pair<long long int, long long int>'} with no trivial copy-assignment [-Wclass-memaccess]
   44 |  memset(ans,-1,sizeof(ans));
      |                           ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from long_mansion.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'pii' {aka 'struct std::pair<long long int, long long int>'} declared here
  211 |     struct pair
      |            ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12120 KB Output is correct
2 Correct 4 ms 12380 KB Output is correct
3 Correct 5 ms 12392 KB Output is correct
4 Correct 5 ms 12124 KB Output is correct
5 Correct 4 ms 12124 KB Output is correct
6 Correct 5 ms 12124 KB Output is correct
7 Correct 5 ms 12124 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12120 KB Output is correct
2 Correct 4 ms 12380 KB Output is correct
3 Correct 5 ms 12392 KB Output is correct
4 Correct 5 ms 12124 KB Output is correct
5 Correct 4 ms 12124 KB Output is correct
6 Correct 5 ms 12124 KB Output is correct
7 Correct 5 ms 12124 KB Output is correct
8 Correct 77 ms 13652 KB Output is correct
9 Correct 80 ms 13584 KB Output is correct
10 Correct 79 ms 13992 KB Output is correct
11 Correct 78 ms 14080 KB Output is correct
12 Correct 72 ms 13904 KB Output is correct
13 Correct 74 ms 13948 KB Output is correct
14 Correct 77 ms 14028 KB Output is correct
15 Correct 75 ms 14012 KB Output is correct
16 Correct 77 ms 14376 KB Output is correct
17 Correct 75 ms 13912 KB Output is correct
18 Correct 79 ms 13912 KB Output is correct
19 Correct 75 ms 13912 KB Output is correct
20 Correct 78 ms 14224 KB Output is correct
21 Correct 72 ms 14232 KB Output is correct
22 Correct 76 ms 13948 KB Output is correct
23 Correct 78 ms 13648 KB Output is correct
24 Correct 76 ms 13652 KB Output is correct
25 Correct 77 ms 13728 KB Output is correct
26 Correct 76 ms 13692 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 20596 KB Output is correct
2 Correct 132 ms 19824 KB Output is correct
3 Correct 132 ms 19344 KB Output is correct
4 Correct 140 ms 20032 KB Output is correct
5 Correct 133 ms 20016 KB Output is correct
6 Correct 120 ms 18568 KB Output is correct
7 Correct 112 ms 18572 KB Output is correct
8 Correct 106 ms 18804 KB Output is correct
9 Correct 112 ms 18716 KB Output is correct
10 Correct 102 ms 18776 KB Output is correct
11 Correct 101 ms 18768 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12120 KB Output is correct
2 Correct 4 ms 12380 KB Output is correct
3 Correct 5 ms 12392 KB Output is correct
4 Correct 5 ms 12124 KB Output is correct
5 Correct 4 ms 12124 KB Output is correct
6 Correct 5 ms 12124 KB Output is correct
7 Correct 5 ms 12124 KB Output is correct
8 Correct 77 ms 13652 KB Output is correct
9 Correct 80 ms 13584 KB Output is correct
10 Correct 79 ms 13992 KB Output is correct
11 Correct 78 ms 14080 KB Output is correct
12 Correct 72 ms 13904 KB Output is correct
13 Correct 74 ms 13948 KB Output is correct
14 Correct 77 ms 14028 KB Output is correct
15 Correct 75 ms 14012 KB Output is correct
16 Correct 77 ms 14376 KB Output is correct
17 Correct 75 ms 13912 KB Output is correct
18 Correct 79 ms 13912 KB Output is correct
19 Correct 75 ms 13912 KB Output is correct
20 Correct 78 ms 14224 KB Output is correct
21 Correct 72 ms 14232 KB Output is correct
22 Correct 76 ms 13948 KB Output is correct
23 Correct 78 ms 13648 KB Output is correct
24 Correct 76 ms 13652 KB Output is correct
25 Correct 77 ms 13728 KB Output is correct
26 Correct 76 ms 13692 KB Output is correct
27 Correct 135 ms 20596 KB Output is correct
28 Correct 132 ms 19824 KB Output is correct
29 Correct 132 ms 19344 KB Output is correct
30 Correct 140 ms 20032 KB Output is correct
31 Correct 133 ms 20016 KB Output is correct
32 Correct 120 ms 18568 KB Output is correct
33 Correct 112 ms 18572 KB Output is correct
34 Correct 106 ms 18804 KB Output is correct
35 Correct 112 ms 18716 KB Output is correct
36 Correct 102 ms 18776 KB Output is correct
37 Correct 101 ms 18768 KB Output is correct
38 Correct 199 ms 38396 KB Output is correct
39 Correct 223 ms 42680 KB Output is correct
40 Correct 184 ms 37380 KB Output is correct
41 Correct 236 ms 39192 KB Output is correct
42 Correct 123 ms 25924 KB Output is correct
43 Correct 146 ms 26256 KB Output is correct
44 Correct 194 ms 33720 KB Output is correct
45 Correct 175 ms 34016 KB Output is correct
46 Correct 199 ms 34212 KB Output is correct
47 Correct 123 ms 26196 KB Output is correct
48 Correct 129 ms 25936 KB Output is correct
49 Correct 190 ms 33960 KB Output is correct
50 Correct 190 ms 33876 KB Output is correct
51 Correct 179 ms 34244 KB Output is correct
52 Correct 136 ms 33744 KB Output is correct
53 Correct 185 ms 41144 KB Output is correct
54 Correct 216 ms 48080 KB Output is correct
55 Correct 161 ms 40908 KB Output is correct