oj.uz

Submission #916814

# Submission time Handle Problem Language Result Execution time Memory
916814 2024-01-26T14:43:34 Z happypotato Long Mansion (JOI17_long_mansion) C++17
25 / 100
 2389 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define ff first
#define ss second
const int mxN = 5e5 + 1;
const int MAX = 1e9, MIN = -1e9;
pii seg[(1 << 20)];
pii a[mxN];
int corr[mxN];
vector<int> keys[mxN];
int n;
void build(int l = 1, int r = n, int idx = 1) {
	if (l == r) {
		seg[idx] = a[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(l, mid, (idx << 1));
	build(mid + 1, r, (idx << 1) | 1);
	seg[idx].ff = min(seg[(idx << 1)].ff, seg[(idx << 1) | 1].ff);
	seg[idx].ss = max(seg[(idx << 1)].ss, seg[(idx << 1) | 1].ss);
}
int querymin(int tl, int tr, int l = 1, int r = n, int idx = 1) {
	if (tl <= l && r <= tr) return seg[idx].ff;
	int mid = (l + r) >> 1;
	int res = MAX;
	if (tl <= mid) res = min(res, querymin(tl, tr, l, mid, (idx << 1)));
	if (tr > mid) res = min(res, querymin(tl, tr, mid + 1, r, (idx << 1) | 1));
	return res;
}
int querymax(int tl, int tr, int l = 1, int r = n, int idx = 1) {
	if (tl <= l && r <= tr) return seg[idx].ss;
	int mid = (l + r) >> 1;
	int res = MIN;
	if (tl <= mid) res = max(res, querymax(tl, tr, l, mid, (idx << 1)));
	if (tr > mid) res = max(res, querymax(tl, tr, mid + 1, r, (idx << 1) | 1));
	return res;
}
map<int, bool> sto[mxN];
bool recur(int x, int y) {
	// cout << x << ' ' << y << endl;
	if (sto[x].find(y) != sto[x].end()) return sto[x][y];
	sto[x][y] = false;
	if (x < y) {
		int req = querymin(x + 1, y);
		if (x <= req) { sto[x].erase(y); return true; }
		if (req == MIN) { sto[x].erase(y); return false; }
		return sto[x][y] = recur(x, req);
	} else if (x > y) {
		int req = querymax(y, x - 1);
		if (req <= x) { sto[x].erase(y); return true; }
		if (req == MAX) { sto[x].erase(y); return false; }
		return sto[x][y] = recur(x, req);
	} else return true;
}
int occur[mxN];
void solve() {
	cin >> n;
	for (int i = 1; i < n; i++) cin >> corr[i];
	for (int i = 1; i <= n; i++) {
		int sz; cin >> sz;
		keys[i].resize(sz);
		for (int &x : keys[i]) cin >> x;
	}
 
	// sweep from left to right, take min of max
	for (int i = 1; i <= n; i++) occur[i] = MIN;
	a[1].ff = MIN;
	for (int i = 1; i < n; i++) {
		for (int x : keys[i]) occur[x] = i;
		a[i + 1].ff = occur[corr[i]];
	}
	// sweep from right to left, take max of min
	for (int i = 1; i <= n; i++) occur[i] = MAX;
	a[n].ss = MAX;
	for (int i = n; i > 1; i--) {
		for (int x : keys[i]) occur[x] = i;
		a[i - 1].ss = occur[corr[i - 1]];
	}
 
	// for (int i = 1; i <= n; i++) {
	// 	cout << i << ": " << a[i].ff << ' ' << a[i].ss << endl;
	// }
	build();
 
	int q; cin >> q;
	while (q--) {
		int x, y;
		cin >> x >> y;
		cout << (recur(x, y) ? "YES\n" : "NO\n");
	}
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	solve();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 41820 KB Output is correct
2 Correct 13 ms 41820 KB Output is correct
3 Correct 14 ms 43868 KB Output is correct
4 Correct 13 ms 41564 KB Output is correct
5 Correct 12 ms 41436 KB Output is correct
6 Correct 12 ms 41560 KB Output is correct
7 Correct 141 ms 59728 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 41820 KB Output is correct
2 Correct 13 ms 41820 KB Output is correct
3 Correct 14 ms 43868 KB Output is correct
4 Correct 13 ms 41564 KB Output is correct
5 Correct 12 ms 41436 KB Output is correct
6 Correct 12 ms 41560 KB Output is correct
7 Correct 141 ms 59728 KB Output is correct
8 Correct 463 ms 64484 KB Output is correct
9 Correct 466 ms 65008 KB Output is correct
10 Correct 476 ms 62700 KB Output is correct
11 Correct 361 ms 61268 KB Output is correct
12 Correct 384 ms 57428 KB Output is correct
13 Correct 134 ms 43344 KB Output is correct
14 Correct 141 ms 43344 KB Output is correct
15 Correct 112 ms 43600 KB Output is correct
16 Correct 121 ms 43444 KB Output is correct
17 Correct 115 ms 43604 KB Output is correct
18 Correct 159 ms 43348 KB Output is correct
19 Correct 174 ms 43504 KB Output is correct
20 Correct 117 ms 43460 KB Output is correct
21 Correct 130 ms 43428 KB Output is correct
22 Correct 143 ms 43344 KB Output is correct
23 Correct 275 ms 63572 KB Output is correct
24 Correct 287 ms 63720 KB Output is correct
25 Correct 316 ms 69208 KB Output is correct
26 Correct 242 ms 58260 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 639 ms 83220 KB Output is correct
2 Correct 612 ms 81356 KB Output is correct
3 Correct 540 ms 76120 KB Output is correct
4 Correct 643 ms 82840 KB Output is correct
5 Correct 686 ms 82724 KB Output is correct
6 Correct 263 ms 63912 KB Output is correct
7 Correct 239 ms 55768 KB Output is correct
8 Correct 206 ms 53844 KB Output is correct
9 Correct 208 ms 54108 KB Output is correct
10 Correct 246 ms 51884 KB Output is correct
11 Correct 199 ms 51860 KB Output is correct

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 41820 KB Output is correct
2 Correct 13 ms 41820 KB Output is correct
3 Correct 14 ms 43868 KB Output is correct
4 Correct 13 ms 41564 KB Output is correct
5 Correct 12 ms 41436 KB Output is correct
6 Correct 12 ms 41560 KB Output is correct
7 Correct 141 ms 59728 KB Output is correct
8 Correct 463 ms 64484 KB Output is correct
9 Correct 466 ms 65008 KB Output is correct
10 Correct 476 ms 62700 KB Output is correct
11 Correct 361 ms 61268 KB Output is correct
12 Correct 384 ms 57428 KB Output is correct
13 Correct 134 ms 43344 KB Output is correct
14 Correct 141 ms 43344 KB Output is correct
15 Correct 112 ms 43600 KB Output is correct
16 Correct 121 ms 43444 KB Output is correct
17 Correct 115 ms 43604 KB Output is correct
18 Correct 159 ms 43348 KB Output is correct
19 Correct 174 ms 43504 KB Output is correct
20 Correct 117 ms 43460 KB Output is correct
21 Correct 130 ms 43428 KB Output is correct
22 Correct 143 ms 43344 KB Output is correct
23 Correct 275 ms 63572 KB Output is correct
24 Correct 287 ms 63720 KB Output is correct
25 Correct 316 ms 69208 KB Output is correct
26 Correct 242 ms 58260 KB Output is correct
27 Correct 639 ms 83220 KB Output is correct
28 Correct 612 ms 81356 KB Output is correct
29 Correct 540 ms 76120 KB Output is correct
30 Correct 643 ms 82840 KB Output is correct
31 Correct 686 ms 82724 KB Output is correct
32 Correct 263 ms 63912 KB Output is correct
33 Correct 239 ms 55768 KB Output is correct
34 Correct 206 ms 53844 KB Output is correct
35 Correct 208 ms 54108 KB Output is correct
36 Correct 246 ms 51884 KB Output is correct
37 Correct 199 ms 51860 KB Output is correct
38 Correct 715 ms 98248 KB Output is correct
39 Correct 846 ms 120596 KB Output is correct
40 Correct 761 ms 106536 KB Output is correct
41 Correct 777 ms 97876 KB Output is correct
42 Correct 247 ms 54356 KB Output is correct
43 Correct 264 ms 56148 KB Output is correct
44 Correct 326 ms 61008 KB Output is correct
45 Correct 313 ms 60244 KB Output is correct
46 Correct 321 ms 59800 KB Output is correct
47 Correct 248 ms 53924 KB Output is correct
48 Correct 334 ms 65604 KB Output is correct
49 Correct 427 ms 70740 KB Output is correct
50 Correct 343 ms 61988 KB Output is correct
51 Correct 303 ms 58960 KB Output is correct
52 Runtime error 2389 ms 262144 KB Execution killed with signal 9
53 Halted 0 ms 0 KB -