Submission #884653

#	Time	Username	Problem	Language	Result	Execution time	Memory
884653		NotLinux	Passport (JOI23_passport)	C++17	0 / 100	40 ms	77908 KiB

passport

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf = 1e9 + 7;
const int N = 3e5 + 7;
struct SegmentExtractor{
	vector < vector < int > > tree;
	vector < int > vis;
	int sz;
	SegmentExtractor(int x){
		sz = x+3;
		tree.assign(4*sz , vector < int >{});
		vis.assign(x+3 , 0);
	}
	void _add(int ind , int l , int r , int ql , int qr , int qind){
		if(l >= ql and r <= qr){
			tree[ind].push_back(qind);
			return;
		}
		else if(l > qr or r < ql){
			return;
		}
		int mid = (l+r)/2;
		_add(ind*2 , l , mid , ql , qr , qind);
		_add(ind*2+1, mid+1 , r , ql , qr , qind);
	}
	void add(int l , int r , int ind){
		_add(1,1,sz,l,r,ind);
	}
	vector < int > ret;
	void _extract(int ind , int l , int r , int p){
		for(auto itr : tree[ind]){
			ret.push_back(itr);
		}
		tree[ind].clear();
		if(l != r){
			int mid = (l+r)/2;
			if(mid >= p)_extract(ind*2,l,mid,p);
			else _extract(ind*2+1,mid+1,r,p);
		}
	}
	vector < int > extract(int p){
		ret.clear();
		vector < int > newret;
		_extract(1,1,sz,p);
		for(auto itr : ret){
			if(vis[itr] == 0){
				newret.push_back(itr);
				vis[itr] = 1;
			}
		}
		return newret;
	}
};
void solve(){
	int n;
	cin >> n;
	pair < int , int > ran[N];
	for(int i = 1;i<=n;i++){
		cin >> ran[i].first >> ran[i].second;
	}
	int sp[2][N];
	for(int i = 0;i<=n;i++){
		sp[0][i] = sp[1][i] = inf;
	}
	//distance from 1
	SegmentExtractor s1(N);
	for(int i = 1;i<=n;i++){
		s1.add(ran[i].first , ran[i].second , i);
	}
	vector < int > cs[N];
	cs[0].push_back(1);
	for(int i = 0;i<N;i++){
		if(cs[i].size()){
			for(auto itr : cs[i]){
				sp[0][itr] = i;
				vector < int > vtmp = s1.extract(itr);
				for(auto itr1 : vtmp){
					if(itr1 == itr)continue;
					cs[i+1].push_back(itr1);
				}
			}
		}
		else break;
	}
	//distance from n
	SegmentExtractor s2(N);
	for(int i = 1;i<=n;i++){
		s2.add(ran[i].first , ran[i].second , i);
		cs[i].clear();
	}
	cs[0].clear();
	cs[0].push_back(n);
	for(int i = 0;i<N;i++){
		if(cs[i].size()){
			for(auto itr : cs[i]){
				sp[1][itr] = i;
				vector < int > vtmp = s2.extract(itr);
				for(auto itr1 : vtmp){
					if(itr1 == itr)continue;
					cs[i+1].push_back(itr1);
				}
			}
		}
		else break;
	}
	//setting up to shortest path
	// cout << "----------" << endl;
	int ans[n+1];
	for(int i = 0;i<=n;i++){
		ans[i] = inf;
	}
	priority_queue < pair < int , int > , vector < pair < int , int > > , greater < pair < int , int > > > pq;
	SegmentExtractor s3(n);
	for(int i = 1;i<=n;i++){
		pq.push({sp[0][i] + sp[1][i] , i});
		s3.add(ran[i].first , ran[i].second , i);
	}
	//doing the shortest path
	while(pq.size()){
		pair < int , int > tmp = pq.top();
		pq.pop();
		if(ans[tmp.second] > tmp.first){
				ans[tmp.second] = tmp.first;
				vector < int > v = s3.extract(tmp.second);
				for(auto itr : v){
					pq.push({tmp.first + 1 , itr});
				}
		}
	}
	//answering the queries
	int q;
	cin >> q;
	while(q--){
		int x;
		cin >> x;
		cout << ans[x] << '\n';
	}
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase = 1;//cin >> testcase;
	while(testcase--)solve();
}

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