oj.uz

Submission #916810

# Submission time Handle Problem Language Result Execution time Memory
916810 2024-01-26T14:42:05 Z happypotato Long Mansion (JOI17_long_mansion) C++17
25 / 100
 2505 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<pii, bool> sto;
bool recur(int x, int y) {
	// cout << x << ' ' << y << endl;
	if (sto.find({x, y}) != sto.end()) return sto[{x, y}];
	sto[{x, y}] = false;
	if (x < y) {
		int req = querymin(x + 1, y);
		if (x <= req) { sto.erase({x, y}); return true; }
		if (req == MIN) { sto.erase({x, y}); return false; }
		return sto[{x, y}] = recur(x, req);
	} else if (x > y) {
		int req = querymax(y, x - 1);
		if (req <= x) { sto.erase({x, y}); return true; }
		if (req == MAX) { sto.erase({x, 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 11 ms 19544 KB Output is correct
2 Correct 11 ms 19548 KB Output is correct
3 Correct 11 ms 19548 KB Output is correct
4 Correct 8 ms 19036 KB Output is correct
5 Correct 7 ms 19036 KB Output is correct
6 Correct 7 ms 19132 KB Output is correct
7 Correct 164 ms 43092 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19544 KB Output is correct
2 Correct 11 ms 19548 KB Output is correct
3 Correct 11 ms 19548 KB Output is correct
4 Correct 8 ms 19036 KB Output is correct
5 Correct 7 ms 19036 KB Output is correct
6 Correct 7 ms 19132 KB Output is correct
7 Correct 164 ms 43092 KB Output is correct
8 Correct 732 ms 52180 KB Output is correct
9 Correct 854 ms 52124 KB Output is correct
10 Correct 760 ms 49388 KB Output is correct
11 Correct 691 ms 44380 KB Output is correct
12 Correct 641 ms 41516 KB Output is correct
13 Correct 202 ms 23380 KB Output is correct
14 Correct 203 ms 23344 KB Output is correct
15 Correct 188 ms 23456 KB Output is correct
16 Correct 205 ms 23244 KB Output is correct
17 Correct 205 ms 23932 KB Output is correct
18 Correct 223 ms 23396 KB Output is correct
19 Correct 241 ms 23380 KB Output is correct
20 Correct 252 ms 23364 KB Output is correct
21 Correct 179 ms 23124 KB Output is correct
22 Correct 196 ms 23120 KB Output is correct
23 Correct 408 ms 50348 KB Output is correct
24 Correct 428 ms 50356 KB Output is correct
25 Correct 517 ms 57616 KB Output is correct
26 Correct 366 ms 43088 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1199 ms 69836 KB Output is correct
2 Correct 1188 ms 70804 KB Output is correct
3 Correct 1025 ms 63964 KB Output is correct
4 Correct 1154 ms 72788 KB Output is correct
5 Correct 1173 ms 72372 KB Output is correct
6 Correct 491 ms 47528 KB Output is correct
7 Correct 427 ms 36292 KB Output is correct
8 Correct 367 ms 33668 KB Output is correct
9 Correct 377 ms 33960 KB Output is correct
10 Correct 355 ms 31064 KB Output is correct
11 Correct 327 ms 31060 KB Output is correct

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19544 KB Output is correct
2 Correct 11 ms 19548 KB Output is correct
3 Correct 11 ms 19548 KB Output is correct
4 Correct 8 ms 19036 KB Output is correct
5 Correct 7 ms 19036 KB Output is correct
6 Correct 7 ms 19132 KB Output is correct
7 Correct 164 ms 43092 KB Output is correct
8 Correct 732 ms 52180 KB Output is correct
9 Correct 854 ms 52124 KB Output is correct
10 Correct 760 ms 49388 KB Output is correct
11 Correct 691 ms 44380 KB Output is correct
12 Correct 641 ms 41516 KB Output is correct
13 Correct 202 ms 23380 KB Output is correct
14 Correct 203 ms 23344 KB Output is correct
15 Correct 188 ms 23456 KB Output is correct
16 Correct 205 ms 23244 KB Output is correct
17 Correct 205 ms 23932 KB Output is correct
18 Correct 223 ms 23396 KB Output is correct
19 Correct 241 ms 23380 KB Output is correct
20 Correct 252 ms 23364 KB Output is correct
21 Correct 179 ms 23124 KB Output is correct
22 Correct 196 ms 23120 KB Output is correct
23 Correct 408 ms 50348 KB Output is correct
24 Correct 428 ms 50356 KB Output is correct
25 Correct 517 ms 57616 KB Output is correct
26 Correct 366 ms 43088 KB Output is correct
27 Correct 1199 ms 69836 KB Output is correct
28 Correct 1188 ms 70804 KB Output is correct
29 Correct 1025 ms 63964 KB Output is correct
30 Correct 1154 ms 72788 KB Output is correct
31 Correct 1173 ms 72372 KB Output is correct
32 Correct 491 ms 47528 KB Output is correct
33 Correct 427 ms 36292 KB Output is correct
34 Correct 367 ms 33668 KB Output is correct
35 Correct 377 ms 33960 KB Output is correct
36 Correct 355 ms 31064 KB Output is correct
37 Correct 327 ms 31060 KB Output is correct
38 Correct 1332 ms 91708 KB Output is correct
39 Correct 1851 ms 120196 KB Output is correct
40 Correct 1611 ms 103408 KB Output is correct
41 Correct 1648 ms 89240 KB Output is correct
42 Correct 363 ms 35136 KB Output is correct
43 Correct 423 ms 37568 KB Output is correct
44 Correct 457 ms 45324 KB Output is correct
45 Correct 449 ms 44628 KB Output is correct
46 Correct 423 ms 43796 KB Output is correct
47 Correct 396 ms 34384 KB Output is correct
48 Correct 566 ms 49728 KB Output is correct
49 Correct 601 ms 59012 KB Output is correct
50 Correct 503 ms 47160 KB Output is correct
51 Correct 412 ms 42780 KB Output is correct
52 Runtime error 2505 ms 262144 KB Execution killed with signal 9
53 Halted 0 ms 0 KB -