제출 #845955

#제출 시각아이디문제언어결과실행 시간메모리
845955QuadrilateralPassport (JOI23_passport)C++14
0 / 100
1 ms604 KiB
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#define MAXN 202020
using namespace std;

int N;

struct pass {
	int L, R;
};

vector<pass> passport;
int Q, ans[MAXN];
int queries[MAXN];

void fastIO() {
	ios_base::sync_with_stdio(0); cin.tie(0);
}

void input() {
	cin >> N;
	passport.resize(N + 1);
	for (int i = 1; i <= N; i++)
		cin >> passport[i].L >> passport[i].R;
	cin >> Q;
	for (int i = 1; i <= Q; i++)
		cin >> queries[i];
}

void init() {
	for (int i = 1; i <= N; i++)
		ans[i] = -1;
}

typedef pair<pair<int, int>, int> ppii;

pair<int, int> rangesum(int i, int l, int r) {
	return { min(passport[i].L, l), max(passport[i].R, r) };
}

void solve() {
	queue<ppii> BFS;
	BFS.push({ { queries[1], queries[1]}, 0 });
	while (BFS.front().second < N) {
		ppii tmp = BFS.front();
		BFS.pop();
		if (tmp.first.first == 1 && tmp.first.second == N) {
			ans[queries[1]] = tmp.second;
			break;
		}
		for (int i = tmp.first.first; i <= tmp.first.second; i++) {
			pair<int, int> tmprange = rangesum(i, tmp.first.first, tmp.first.second);
			if (tmprange.first == tmp.first.first && tmprange.second == tmp.first.second) continue;
			BFS.push({ tmprange, tmp.second + 1 });
		}
	}
}

void output() {
	for (int i = 1; i <= Q; i++)
		cout << ans[queries[i]] << '\n';
}

int main() {
	fastIO();
	input();
	solve();
	output();
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...