Submission #796732

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
796732	2023-07-28T16:31:24 Z	GusterGoose27	Passport (JOI23_passport)	C++17	22 / 100	685 ms	76564 KB

passport

#include <bits/stdc++.h>

using namespace std;

const int MAXN = (1<<18)+5;
const int inf = 1e9+7;

typedef pair<int, int> pii;

int dist[2][2*MAXN];
int sumdist[2*MAXN];
int n, m;

vector<pii> edges[2*MAXN];

void build() {
	for (int i = 1; i < m; i++) {
		edges[2*i].push_back(pii(i, 0));
		edges[2*i+1].push_back(pii(i, 0));
	}
}

void assign(int i, int l, int r) {
	for (; r > l; l /= 2, r /= 2) {
		if (l & 1) edges[l++].push_back(pii(i, 1));
		if (r & 1) edges[--r].push_back(pii(i, 1));
	}
}

void dijkstra(int curdist[]) {
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	for (int i = 0; i < 2*m; i++)
		pq.push(pii(curdist[i], i));
	while (!pq.empty()) {
		pii tp = pq.top();
		pq.pop();
		int cur = tp.second;
		if (tp.first > curdist[cur]) continue;
		for (pii p: edges[cur]) {
			int nxtdist = tp.first+p.second;
			if (nxtdist < curdist[p.first]) {
				curdist[p.first] = nxtdist;
				pq.push(pii(nxtdist, p.first));
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n;
	m = 1;
	for (; m < n; m *= 2);
	build();
	fill(dist[0], dist[0]+2*m, inf);
	fill(dist[1], dist[1]+2*m, inf);
	for (int i = 0; i < n; i++) {
		int l, r; cin >> l >> r;
		l--; r--;
		// for (int j = l+n; j <= r+n; j++) edges[j].push_back(pii(i+n, 1));
		assign(i+m, l+m, r+m+1);
		if (l == 0) dist[0][i+m] = 0;
		if (r == n-1) dist[1][i+m] = 0;
	}
	dijkstra(dist[0]);
	dijkstra(dist[1]);
	for (int i = 0; i < 2*m; i++) {
		sumdist[i] = min(inf, dist[0][i]+dist[1][i]);
	}
	dijkstra(sumdist);
	int q; cin >> q;
	for (int i = 0; i < q; i++) {
		int s; cin >> s; s += m-1;
		cout << ((sumdist[s] < inf) ? sumdist[s]+1 : -1) << '\n';
	}
}

Subtask #1

6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	12628 KB	Output is correct
2	Correct	6 ms	12628 KB	Output is correct
3	Correct	7 ms	12628 KB	Output is correct
4	Correct	685 ms	76564 KB	Output is correct
5	Correct	451 ms	53672 KB	Output is correct
6	Correct	374 ms	50272 KB	Output is correct
7	Correct	284 ms	60260 KB	Output is correct
8	Correct	243 ms	62300 KB	Output is correct

Subtask #2

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	12628 KB	Output is correct
2	Correct	6 ms	12540 KB	Output is correct
3	Correct	6 ms	12628 KB	Output is correct
4	Correct	6 ms	12628 KB	Output is correct
5	Correct	6 ms	12628 KB	Output is correct
6	Correct	6 ms	12628 KB	Output is correct
7	Correct	8 ms	12628 KB	Output is correct
8	Correct	8 ms	12772 KB	Output is correct
9	Correct	6 ms	12628 KB	Output is correct
10	Correct	6 ms	12628 KB	Output is correct
11	Correct	7 ms	12628 KB	Output is correct
12	Correct	7 ms	12628 KB	Output is correct
13	Correct	6 ms	12756 KB	Output is correct
14	Correct	6 ms	12628 KB	Output is correct
15	Correct	6 ms	12628 KB	Output is correct

Subtask #3

0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	12628 KB	Output is correct
2	Correct	6 ms	12540 KB	Output is correct
3	Correct	6 ms	12628 KB	Output is correct
4	Correct	6 ms	12628 KB	Output is correct
5	Correct	6 ms	12628 KB	Output is correct
6	Correct	6 ms	12628 KB	Output is correct
7	Correct	8 ms	12628 KB	Output is correct
8	Correct	8 ms	12772 KB	Output is correct
9	Correct	6 ms	12628 KB	Output is correct
10	Correct	6 ms	12628 KB	Output is correct
11	Correct	7 ms	12628 KB	Output is correct
12	Correct	7 ms	12628 KB	Output is correct
13	Correct	6 ms	12756 KB	Output is correct
14	Correct	6 ms	12628 KB	Output is correct
15	Correct	6 ms	12628 KB	Output is correct
16	Incorrect	11 ms	13384 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #4

0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	12628 KB	Output is correct
2	Correct	6 ms	12540 KB	Output is correct
3	Correct	6 ms	12628 KB	Output is correct
4	Correct	6 ms	12628 KB	Output is correct
5	Correct	6 ms	12628 KB	Output is correct
6	Correct	6 ms	12628 KB	Output is correct
7	Correct	8 ms	12628 KB	Output is correct
8	Correct	8 ms	12772 KB	Output is correct
9	Correct	6 ms	12628 KB	Output is correct
10	Correct	6 ms	12628 KB	Output is correct
11	Correct	7 ms	12628 KB	Output is correct
12	Correct	7 ms	12628 KB	Output is correct
13	Correct	6 ms	12756 KB	Output is correct
14	Correct	6 ms	12628 KB	Output is correct
15	Correct	6 ms	12628 KB	Output is correct
16	Incorrect	11 ms	13384 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #5

0 / 46.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	12628 KB	Output is correct
2	Correct	6 ms	12628 KB	Output is correct
3	Correct	7 ms	12628 KB	Output is correct
4	Correct	685 ms	76564 KB	Output is correct
5	Correct	451 ms	53672 KB	Output is correct
6	Correct	374 ms	50272 KB	Output is correct
7	Correct	284 ms	60260 KB	Output is correct
8	Correct	243 ms	62300 KB	Output is correct
9	Correct	6 ms	12628 KB	Output is correct
10	Correct	6 ms	12540 KB	Output is correct
11	Correct	6 ms	12628 KB	Output is correct
12	Correct	6 ms	12628 KB	Output is correct
13	Correct	6 ms	12628 KB	Output is correct
14	Correct	6 ms	12628 KB	Output is correct
15	Correct	8 ms	12628 KB	Output is correct
16	Correct	8 ms	12772 KB	Output is correct
17	Correct	6 ms	12628 KB	Output is correct
18	Correct	6 ms	12628 KB	Output is correct
19	Correct	7 ms	12628 KB	Output is correct
20	Correct	7 ms	12628 KB	Output is correct
21	Correct	6 ms	12756 KB	Output is correct
22	Correct	6 ms	12628 KB	Output is correct
23	Correct	6 ms	12628 KB	Output is correct
24	Incorrect	11 ms	13384 KB	Output isn't correct
25	Halted	0 ms	0 KB	-