Submission #783345

#	Time	Username	Problem	Language	Result	Execution time	Memory
783345		fuad27	Passport (JOI23_passport)	C++17	100 / 100	317 ms	20728 KiB

passport

#include<bits/stdc++.h>
using namespace std;
const int N=200010;
const int INF=1e9+10;
struct pass {
	int l, r, i;
};
int n;
struct ST {
	vector<int> mx;
	vector<pass> p;
	int n=1;
	ST(vector<pass> v) {
		while(n<(int)v.size()) {
			n*=2;
		}
		p=v;
		mx.resize(2*n,-1);
		for(int i = 0;i<(int)v.size();i++) {
			mx[i+n]=v[i].r;
		}
		for(int i = n-1;i>=0;i--)mx[i]=max(mx[2*i], mx[2*i+1]);
	}
	void get(vector<int>&a, int idx, int v=1, int l=0, int r=-1) {
		if(r<0)r+=n;	
		if(l>=(int)p.size() or p[l].l>idx or mx[v]<idx) {
			return;
		}
		else if(l==r){
			a.push_back(l);
			mx[v]=-1;
			return;
		}
		else {
			int tm=(l+r)/2;
			get(a,idx,2*v,l,tm);
			get(a,idx,2*v+1,tm+1,r);
			mx[v]=max(mx[2*v],mx[2*v+1]);
		}
	}
};
vector<pass> p;
// [0,n-1] -> country
// [n,2n-1] -> passport
void dijkstra(vector<int> &dist) {
	ST s(p);
	for(int i = n;i<2*n;i++) {
		dist[p[i-n].i]=min(dist[p[i-n].i], dist[i]+1);
	}
	priority_queue<pair<int,int>,vector<pair<int,int>>, greater<pair<int,int>>> pq;
	for(int i = 0;i<n;i++)pq.push({dist[i],i});
	while(pq.size()) {
		auto at=pq.top();
		pq.pop();
		if(at.first>dist[at.second])continue;
		vector<int> cc;
		s.get(cc,at.second);
		for(auto i:cc) {
			if(dist[i+n]>at.first) {
				dist[i+n]=at.first;
				if(dist[p[i].i]>dist[i+n]+1) {
					dist[p[i].i]=dist[i+n]+1;
					pq.push({dist[p[i].i], p[i].i});
				}
			}
		}
	}
}
int main () {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n;
	p.resize(n);
	for(int i = 0;i<n;i++){
		cin >> p[i].l >> p[i].r;
		p[i].l--,p[i].r--;
		p[i].i=i;
	}
	sort(p.begin(),p.end(), [](const pass &A, const pass &B) {
		return A.l<B.l;
	});
	vector<int> dl(n+n, INF), dr(n+n,INF);	
	dl[0]=0, dr[n-1]=0;
	dijkstra(dl);
	dijkstra(dr);
	vector<int> d(n+n);
	for(int i = 0;i<2*n;i++) {
		d[i]=dl[i]+dr[i];
	}
	dijkstra(d);
	int q;
	cin >> q;
	while(q--) {
		int x;
		cin >> x;
		if(d[x-1]>=INF)d[x-1]=-1;
		cout << d[x-1] << "\n";
	}
}

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