Submission #845955

#	Time	Username	Problem	Language	Result	Execution time	Memory
845955		Quadrilateral	Passport (JOI23_passport)	C++14	0 / 100	1 ms	604 KiB

passport

#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;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 8
• Subtask 5: 0 / 46