oj.uz

Submission #916802

# Submission time Handle Problem Language Result Execution time Memory
916802 2024-01-26T14:38:40 Z happypotato Long Mansion (JOI17_long_mansion) C++17
20 / 100
 3000 ms 26196 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) return sto[{x, y}] = true;
		if (req == MIN) return sto[{x, y}] = false;
		return sto[{x, y}] = recur(x, req);
	} else if (x > y) {
		int req = querymax(y, x - 1);
		if (req <= x) return sto[{x, y}] = true;
		if (req == MAX) return sto[{x, y}] = 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");
		sto.clear();
	}
}
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 10 ms 18776 KB Output is correct
2 Correct 9 ms 18860 KB Output is correct
3 Correct 8 ms 19032 KB Output is correct
4 Correct 7 ms 18992 KB Output is correct
5 Correct 7 ms 18780 KB Output is correct
6 Correct 7 ms 19020 KB Output is correct
7 Correct 393 ms 19184 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 18776 KB Output is correct
2 Correct 9 ms 18860 KB Output is correct
3 Correct 8 ms 19032 KB Output is correct
4 Correct 7 ms 18992 KB Output is correct
5 Correct 7 ms 18780 KB Output is correct
6 Correct 7 ms 19020 KB Output is correct
7 Correct 393 ms 19184 KB Output is correct
8 Correct 346 ms 20592 KB Output is correct
9 Correct 356 ms 20460 KB Output is correct
10 Correct 325 ms 20648 KB Output is correct
11 Correct 285 ms 20816 KB Output is correct
12 Correct 271 ms 20596 KB Output is correct
13 Correct 176 ms 20564 KB Output is correct
14 Correct 162 ms 20688 KB Output is correct
15 Correct 264 ms 20852 KB Output is correct
16 Correct 161 ms 20820 KB Output is correct
17 Correct 287 ms 20720 KB Output is correct
18 Correct 189 ms 20624 KB Output is correct
19 Correct 178 ms 20564 KB Output is correct
20 Correct 207 ms 20816 KB Output is correct
21 Correct 147 ms 20864 KB Output is correct
22 Correct 165 ms 20544 KB Output is correct
23 Execution timed out 3047 ms 19248 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 486 ms 25940 KB Output is correct
2 Correct 475 ms 25880 KB Output is correct
3 Correct 416 ms 26144 KB Output is correct
4 Correct 482 ms 26000 KB Output is correct
5 Correct 480 ms 25896 KB Output is correct
6 Correct 311 ms 25856 KB Output is correct
7 Correct 246 ms 26060 KB Output is correct
8 Correct 230 ms 26168 KB Output is correct
9 Correct 229 ms 26196 KB Output is correct
10 Correct 197 ms 26196 KB Output is correct
11 Correct 215 ms 26060 KB Output is correct

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 18776 KB Output is correct
2 Correct 9 ms 18860 KB Output is correct
3 Correct 8 ms 19032 KB Output is correct
4 Correct 7 ms 18992 KB Output is correct
5 Correct 7 ms 18780 KB Output is correct
6 Correct 7 ms 19020 KB Output is correct
7 Correct 393 ms 19184 KB Output is correct
8 Correct 346 ms 20592 KB Output is correct
9 Correct 356 ms 20460 KB Output is correct
10 Correct 325 ms 20648 KB Output is correct
11 Correct 285 ms 20816 KB Output is correct
12 Correct 271 ms 20596 KB Output is correct
13 Correct 176 ms 20564 KB Output is correct
14 Correct 162 ms 20688 KB Output is correct
15 Correct 264 ms 20852 KB Output is correct
16 Correct 161 ms 20820 KB Output is correct
17 Correct 287 ms 20720 KB Output is correct
18 Correct 189 ms 20624 KB Output is correct
19 Correct 178 ms 20564 KB Output is correct
20 Correct 207 ms 20816 KB Output is correct
21 Correct 147 ms 20864 KB Output is correct
22 Correct 165 ms 20544 KB Output is correct
23 Execution timed out 3047 ms 19248 KB Time limit exceeded
24 Halted 0 ms 0 KB -