oj.uz

Submission #844792

# Submission time Handle Problem Language Result Execution time Memory
844792 2023-09-06T00:41:58 Z Quadrilateral Passport (JOI23_passport) C++14
0 / 100
 2000 ms 3040 KB 
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#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;
}

void solve() {
	init();
	int tmp = 1, destinL = passport[queries[1]].L, destinR = passport[queries[1]].R, minL = destinL, maxR = destinR;
	bool flag = 0;
	while (destinL != 1 || destinR != N) {
		tmp++;
		for (int i = destinL; i <= destinR; i++) {
			minL = min(minL, passport[i].L);
			maxR = max(maxR, passport[i].R);
		}
		if (minL == destinL && maxR == destinR) {
			flag = 1;
			break;
		}
		destinL = minL;
		destinR = maxR;
	}
	ans[queries[1]] = tmp;
	if (flag) ans[queries[1]] = -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 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 24 ms 3040 KB Output is correct
5 Correct 1544 ms 2532 KB Output is correct
6 Execution timed out 2069 ms 2648 KB Time limit exceeded
7 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 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 464 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 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 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 464 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 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 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 464 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 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 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 24 ms 3040 KB Output is correct
5 Correct 1544 ms 2532 KB Output is correct
6 Execution timed out 2069 ms 2648 KB Time limit exceeded
7 Halted 0 ms 0 KB -