oj.uz

답안 #283090

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
283090 2020-08-25T09:54:13 Z Berted Long Mansion (JOI17_long_mansion) C++14
0 / 100
 278 ms 26352 KB 
#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) {lel.fst = prev(s1.end()) -> fst; s1.erase(prev(s1.end()));}
	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) {s1.insert({lel.fst, x - 1});}
		if (x < lel.snd) {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()));}
		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
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 12288 KB Output is correct
2 Correct 11 ms 12416 KB Output is correct
3 Correct 13 ms 12416 KB Output is correct
4 Incorrect 11 ms 12288 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 12288 KB Output is correct
2 Correct 11 ms 12416 KB Output is correct
3 Correct 13 ms 12416 KB Output is correct
4 Incorrect 11 ms 12288 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 234 ms 26352 KB Output is correct
2 Correct 278 ms 25708 KB Output is correct
3 Correct 236 ms 25752 KB Output is correct
4 Correct 232 ms 25964 KB Output is correct
5 Correct 235 ms 25964 KB Output is correct
6 Correct 202 ms 24300 KB Output is correct
7 Incorrect 189 ms 24364 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 12288 KB Output is correct
2 Correct 11 ms 12416 KB Output is correct
3 Correct 13 ms 12416 KB Output is correct
4 Incorrect 11 ms 12288 KB Output isn't correct
5 Halted 0 ms 0 KB -