제출 #283119

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
283119		Berted	Long Mansion (JOI17_long_mansion)	C++14	100 / 100	722 ms	39140 KiB

long_mansion

#include <iostream>
#include <set>
#include <queue>
#include <algorithm>
#include <vector>
#define pii pair<int, int>
#define fst first
#define snd second
#define vi vector<int>
using namespace std;

/*
	Idea :
	We can transform this problem into a graph traversal problem
	Node is defined as (L, R) which is the range currently accessible
	The edges have a special property, which can be exploited, 
	such that we can maintain a data structure where we can query the rightmost cell reachable from a node.
	Once we determine the rightmost reachable cell, we can determine the leftmost reachable cell. 
*/

int n, q;
int val[500001], goL[500001], goR[500001];
vi pos[500001];
int L[500001], R[500001];
set<pii> s1, s2;
priority_queue<pii> pq;

inline void ins(int x)
{
	pii lel = {x, x};
	if (s1.size() && prev(s1.end()) -> snd + 1 == x) {lel.fst = prev(s1.end()) -> fst; s1.erase(prev(s1.end()));}
	//cout << "insert " << lel.fst << " " << lel.snd << "\n";
	s1.insert(lel);
}

inline void del(int x)
{
	auto it = s1.upper_bound({x + 1, -1});
	if (it != s1.begin())
	{
		pii lel = *prev(it); s1.erase(prev(it));
		if (lel.fst < x) 
		{
			//cout << "insert " << lel.fst << " " << x - 1 << "\n";
			s1.insert({lel.fst, x - 1});
		}
		if (x < lel.snd) 
		{
			//cout << "insert " << x + 1 << " " << lel.snd << "\n";
			s1.insert({x + 1, lel.snd});
		}
	}
}

int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 0; i < n - 1; i++) {cin >> val[i];}
	for (int i = 0; i < n; i++)
	{
		int x; cin >> x;
		for (int j = 0; j < x; j++)
		{
			int k; cin >> k; pos[k].push_back(i);
		}
	}
	for (int i = 0; i < n - 1; i++)
	{
		auto it = upper_bound(pos[val[i]].begin(), pos[val[i]].end(), i);
		if (it != pos[val[i]].begin()) {goR[i] = *prev(it);}
		else {goR[i] = -1;}
		if (it != pos[val[i]].end()) {goL[i] = *it;}
		else {goL[i] = n;}
		if (goL[i] < n) {pq.push({goL[i], i}); ins(i);}
		//cout << "Bridge " << i << " " << goL[i] << " " << goR[i] << "\n";
	}
	s2.insert({0, n - 1}); R[n - 1] = n - 1;
	for (int i = n - 2; i >= 0; i--)
	{
		while (pq.size() && pq.top().fst > i)
		{
			del(pq.top().snd); pq.pop();
		}
		auto it = s1.upper_bound({goR[i] + 1, -1});
		int np = goR[i] + 1;
		if (it != s1.begin()) 
		{
			if (prev(it) -> fst <= goR[i] && goR[i] <= prev(it) -> snd) np = prev(it) -> snd + 2;
		}
		while (s2.size() && prev(s2.end()) -> fst >= np) {s2.erase(prev(s2.end()));}
		//cout << np << " " << i << "\n";
		if (np <= i) s2.insert({np, i});
		R[i] = prev(s2.end()) -> snd;
		//cout << i << " " << R[i] << "\n";
	}
	vector<pii> s;
	for (int i = 0; i < n; i++)
	{
		L[i] = i;
		auto it = upper_bound(s.begin(), s.end(), make_pair(R[i], n), greater<pii>());
		if (it != s.end()) 
		{
			if (it == s.begin()) {L[i] = 0;}
			else {L[i] = prev(it) -> snd + 1;}
		}
		if (i + 1 < n)
		{
			while (s.size() && s.back().fst <= goL[i]) {s.pop_back();}
			s.push_back({goL[i], i});
		}
		//cout << i << " " << L[i] << " " << R[i] << "\n";
	}
	cin >> q;
	while (q--)
	{
		int S, T; cin >> S >> T; S--; T--;
		if (L[S] <= T && T <= R[S]) cout << "YES\n";
		else cout << "NO\n";
	}
	return 0;
}

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