Submission #796732

#	Time	Username	Problem	Language	Result	Execution time	Memory
796732		GusterGoose27	Passport (JOI23_passport)	C++17	22 / 100	685 ms	76564 KiB

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 / 6
• Subtask 2: 16 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 8
• Subtask 5: 0 / 46