oj.uz

답안 #916796

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
916796 2024-01-26T14:32:46 Z happypotato Long Mansion (JOI17_long_mansion) C++17
0 / 100
 392 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;
}
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;
	}

	map<int, int> mp;
	// sweep from left to right, take min of max
	mp.clear();
	a[1].ff = MIN;
	for (int i = 1; i < n; i++) {
		for (int x : keys[i]) mp[x] = i;
		a[i + 1].ff = (mp.find(corr[i]) == mp.end() ? MIN : mp[corr[i]]);
	}
	// sweep from right to left, take max of min
	mp.clear();
	a[n].ss = MAX;
	for (int i = n; i > 1; i--) {
		for (int x : keys[i]) mp[x] = i;
		a[i - 1].ss = (mp.find(corr[i - 1]) == mp.end() ? MAX : mp[corr[i - 1]]);
	}

	// for (int i = 1; i <= n; i++) {
	// 	cout << i << ": " << a[i].ff << ' ' << a[i].ss << endl;
	// }
	build();

	int q; cin >> q;
	map<pii, bool> sto;
	function<bool(int, int)> recur = [&](int x, int y) -> bool {
		// cout << x << ' ' << y << endl;
		if (sto.find({x, y}) != sto.end()) return sto[{x, y}];
		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;
	};

	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
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 292 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 292 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 392 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 292 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -