Submission #717106

#	Time	Username	Problem	Language	Result	Execution time	Memory
717106		ymm	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	305 ms	56476 KiB

long_mansion

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 500'010;

namespace seg {
	int t[4*N];
	int n;

	void build(int *a, int i, int b, int e) {
		if (e-b == 1) {
			t[i] = a[b];
			return;
		}
		build(a, 2*i+1, b, (b+e)/2);
		build(a, 2*i+2, (b+e)/2, e);
		t[i] = min(t[2*i+1], t[2*i+2]);
	}
	void build(int *a, int len) {
		n = len;
		build(a, 0, 0, n);
	}

	int get(int l, int r, int x, int i, int b, int e) {
		if (r <= b || e <= l || t[i] >= x)
			return r;
		if (e-b == 1)
			return b;
		int ans = r;
		ans = get(l, r, x, 2*i+1, b, (b+e)/2);
		if (ans != r)
			return ans;
		ans = get(l, r, x, 2*i+2, (b+e)/2, e);
		if (ans != r)
			return ans;
		return r;
	}
	int get(int l, int r, int x) {
		if (l == r)
			return r;
		return get(l, r, x, 0, 0, n);
	}
}

int col[N], lst[N];
int left_key[N], right_key[N];
int L[N], R[N];
vector<int> keys[N];
int n;

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n;
	Loop (i,0,n-1) {
		cin >> col[i];
		--col[i];
	}
	Loop (i,0,n) {
		int k;
		cin >> k;
		while (k--) {
			int x;
			cin >> x;
			keys[i].push_back(x-1);
		}
	}

	fill(lst, lst+n, -1);
	Loop (i,0,n-1) {
		for (int k : keys[i])
			lst[k] = i;
		left_key[i] = lst[col[i]];
	}
	fill(lst, lst+n, n);
	LoopR (i,1,n) {
		for (int k : keys[i])
			lst[k] = i;
		right_key[i-1] = lst[col[i-1]];
	}
	seg::build(left_key, n-1);

	Loop (i,0,n) {
		L[i] = R[i] = i;
		for (;;) {
			int j = seg::get(R[i], n-1, L[i]);
			R[i] = j;
			if (L[i] == 0 || right_key[L[i]-1] > R[i])
				break;
			R[i] = max(R[i], R[L[i]-1]);
			L[i] = min(L[i], L[L[i]-1]);
		}
	}

	int q;
	cin >> q;
	while (q--) {
		int x, y;
		cin >> x >> y;
		--x; --y;
		cout << (L[x] <= y && y <= R[x]? "YES": "NO") << '\n';
	}
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 15 / 15
• Subtask 4: 75 / 75