oj.uz

Submission #845955

# Submission time Handle Problem Language Result Execution time Memory
845955 2023-09-07T00:55:13 Z Quadrilateral Passport (JOI23_passport) C++14
0 / 100
 1 ms 604 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 1 ms 604 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Runtime error 1 ms 600 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Runtime error 1 ms 600 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Runtime error 1 ms 600 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 1 ms 604 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -