oj.uz

Submission #723998

# Submission time Handle Problem Language Result Execution time Memory
723998 2023-04-14T15:15:57 Z NothingXD Long Mansion (JOI17_long_mansion) C++17
100 / 100
 485 ms 35576 KB 
/*

   Wei Wai Wei Wai
   Zumigat nan damu dimi kwayt rayt

*/

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;
/*typedef __uint128_t L;
  struct FastMod {
  ull b, m;
  FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
  ull reduce(ull a) {
  ull q = (ull)((L(m) * a) >> 64);
  ull r = a - q * b; // can be proven that 0 <= r < 2*b
  return r >= b ? r - b : r;
  }
  };
  FastMod FM(2);
  */
void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
	cerr << " " << H;
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
#define F first
#define S second

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 5e5 + 10;

int n, q, L[maxn], R[maxn], a[maxn];
vector<int> val[maxn];
bool mark[maxn];

void solve(int l, int r){
	if (l + 1 == r){
		L[l] = R[l] = l;
		return;
	}
	int mid = (l + r) >> 1;
	solve(l, mid);
	solve(mid, r);
	int ptl = mid, ptr = mid-1;
	for (int i = mid; i < r; i++){
		if (L[i] != mid) continue;
		while(ptr < R[i]){
			ptr++;
			for (auto x: val[ptr]) mark[x] = true;
		}
		while((ptl > l && mark[a[ptl-1]]) || (ptr + 1 < r && mark[a[ptr]])){
			if (ptl > l && mark[a[ptl-1]]){
				ptl--;
				for (auto x: val[ptl]) mark[x] = true;
			}
			if (ptr + 1 < r && mark[a[ptr]]){
				ptr++;
				for (auto x: val[ptr]) mark[x] = true;
			}
		}
		L[i] = ptl, R[i] = ptr;
	}
	for (int i = l; i < r; i++) for (auto x: val[i]) mark[x] = false;
	ptl = mid, ptr = mid-1;
	for (int i = mid-1; i >= l; i--){
		if (R[i] != mid-1) continue;
		while(ptl > L[i]){
			ptl--;
			for (auto x: val[ptl]) mark[x] = true;
		}
		while((ptl > l && mark[a[ptl-1]]) || (ptr + 1 < r && mark[a[ptr]])){
			if (ptl > l && mark[a[ptl-1]]){
				ptl--;
				for (auto x: val[ptl]) mark[x] = true;
			}
			if (ptr + 1 < r && mark[a[ptr]]){
				ptr++;
				for (auto x: val[ptr]) mark[x] = true;
			}
		}
		L[i] = ptl, R[i] = ptr;
	}
	for (int i = l; i < r; i++) for (auto x: val[i]) mark[x] = false;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);

	cin >> n;
	for (int i = 1; i < n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++){
		int k; cin >> k;
		for (int j = 0; j < k; j++){
			int x; cin >> x;
			val[i].push_back(x);
		}
	}

	solve(1, n+1);
	cin >> q;
	while(q--){
		int u, v; cin >> u >> v;
		cout << (L[u] <= v && v <= R[u]? "YES\n": "NO\n");
	}

	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12212 KB Output is correct
2 Correct 10 ms 12244 KB Output is correct
3 Correct 11 ms 12404 KB Output is correct
4 Correct 10 ms 12212 KB Output is correct
5 Correct 9 ms 12244 KB Output is correct
6 Correct 9 ms 12244 KB Output is correct
7 Correct 9 ms 12244 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12212 KB Output is correct
2 Correct 10 ms 12244 KB Output is correct
3 Correct 11 ms 12404 KB Output is correct
4 Correct 10 ms 12212 KB Output is correct
5 Correct 9 ms 12244 KB Output is correct
6 Correct 9 ms 12244 KB Output is correct
7 Correct 9 ms 12244 KB Output is correct
8 Correct 98 ms 13844 KB Output is correct
9 Correct 97 ms 13932 KB Output is correct
10 Correct 93 ms 14072 KB Output is correct
11 Correct 102 ms 14244 KB Output is correct
12 Correct 95 ms 14044 KB Output is correct
13 Correct 92 ms 14104 KB Output is correct
14 Correct 101 ms 14156 KB Output is correct
15 Correct 91 ms 14148 KB Output is correct
16 Correct 94 ms 14420 KB Output is correct
17 Correct 90 ms 14068 KB Output is correct
18 Correct 92 ms 14132 KB Output is correct
19 Correct 93 ms 14188 KB Output is correct
20 Correct 92 ms 14304 KB Output is correct
21 Correct 83 ms 14412 KB Output is correct
22 Correct 89 ms 14124 KB Output is correct
23 Correct 88 ms 14008 KB Output is correct
24 Correct 97 ms 14024 KB Output is correct
25 Correct 94 ms 13984 KB Output is correct
26 Correct 92 ms 13900 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 18880 KB Output is correct
2 Correct 256 ms 18872 KB Output is correct
3 Correct 296 ms 18840 KB Output is correct
4 Correct 264 ms 18820 KB Output is correct
5 Correct 258 ms 18856 KB Output is correct
6 Correct 186 ms 18344 KB Output is correct
7 Correct 203 ms 18620 KB Output is correct
8 Correct 183 ms 18552 KB Output is correct
9 Correct 189 ms 18564 KB Output is correct
10 Correct 176 ms 18576 KB Output is correct
11 Correct 178 ms 18612 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12212 KB Output is correct
2 Correct 10 ms 12244 KB Output is correct
3 Correct 11 ms 12404 KB Output is correct
4 Correct 10 ms 12212 KB Output is correct
5 Correct 9 ms 12244 KB Output is correct
6 Correct 9 ms 12244 KB Output is correct
7 Correct 9 ms 12244 KB Output is correct
8 Correct 98 ms 13844 KB Output is correct
9 Correct 97 ms 13932 KB Output is correct
10 Correct 93 ms 14072 KB Output is correct
11 Correct 102 ms 14244 KB Output is correct
12 Correct 95 ms 14044 KB Output is correct
13 Correct 92 ms 14104 KB Output is correct
14 Correct 101 ms 14156 KB Output is correct
15 Correct 91 ms 14148 KB Output is correct
16 Correct 94 ms 14420 KB Output is correct
17 Correct 90 ms 14068 KB Output is correct
18 Correct 92 ms 14132 KB Output is correct
19 Correct 93 ms 14188 KB Output is correct
20 Correct 92 ms 14304 KB Output is correct
21 Correct 83 ms 14412 KB Output is correct
22 Correct 89 ms 14124 KB Output is correct
23 Correct 88 ms 14008 KB Output is correct
24 Correct 97 ms 14024 KB Output is correct
25 Correct 94 ms 13984 KB Output is correct
26 Correct 92 ms 13900 KB Output is correct
27 Correct 262 ms 18880 KB Output is correct
28 Correct 256 ms 18872 KB Output is correct
29 Correct 296 ms 18840 KB Output is correct
30 Correct 264 ms 18820 KB Output is correct
31 Correct 258 ms 18856 KB Output is correct
32 Correct 186 ms 18344 KB Output is correct
33 Correct 203 ms 18620 KB Output is correct
34 Correct 183 ms 18552 KB Output is correct
35 Correct 189 ms 18564 KB Output is correct
36 Correct 176 ms 18576 KB Output is correct
37 Correct 178 ms 18612 KB Output is correct
38 Correct 383 ms 31056 KB Output is correct
39 Correct 343 ms 35324 KB Output is correct
40 Correct 311 ms 26748 KB Output is correct
41 Correct 485 ms 35576 KB Output is correct
42 Correct 175 ms 18344 KB Output is correct
43 Correct 224 ms 18324 KB Output is correct
44 Correct 251 ms 22728 KB Output is correct
45 Correct 272 ms 22804 KB Output is correct
46 Correct 279 ms 22808 KB Output is correct
47 Correct 218 ms 18448 KB Output is correct
48 Correct 213 ms 18416 KB Output is correct
49 Correct 282 ms 22700 KB Output is correct
50 Correct 296 ms 22704 KB Output is correct
51 Correct 340 ms 22796 KB Output is correct
52 Correct 226 ms 22608 KB Output is correct
53 Correct 294 ms 27012 KB Output is correct
54 Correct 362 ms 31432 KB Output is correct
55 Correct 278 ms 26824 KB Output is correct