Submission #763251

#	Time	Username	Problem	Language	Result	Execution time	Memory
763251		sentheta	Passport (JOI23_passport)	C++17	100 / 100	435 ms	40780 KiB

passport

// author : sentheta aka vanwij
#ifdef VANWIJ
	#include"/home/user/code/bits/stdc++.h"
#else
	#include"bits/stdc++.h"
#endif
using namespace std;

#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second

static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define dbg(x) if(1) cout << "?" << #x << " : " << (x) << endl << flush;

// #define int long long
// const Int MOD = 1e9+7;
const Int MOD = 998244353;
Int bpow(Int a,Int b){
	Int ret = 1;
	for(;b; a=a*a%MOD,b/=2) if(b&1) ret = ret*a%MOD;
	return ret;
}
Int inv(Int a){return bpow(a,MOD-2);}

void solve(); int TC, ALLTC;
signed main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout << fixed << setprecision(7);
	// cin >> ALLTC; for(TC=1; TC<=ALLTC; TC++) solve(); return 0;
	solve();
}












const int INF = 1e9;
const int N = 2e5+5;

int n;
int a[N], b[N];

int to1[N], ton[N];
int ans[N];

bool vis[N];

// {-dist, node}
priority_queue<pii> pq;

// segtree
#define lc (v+1)
#define rc (v+2*(mid-tl+1))
#define mid (tl+tr)/2
V<int> segs[2*N];
bool stvis[2*N];
void insert(int i,int v=0,int tl=1,int tr=n){
	if(b[i]<tl || tr<a[i]) return;
	if(a[i]<=tl && tr<=b[i]){
		// cout << tl _ tr << nl;
		segs[v].push_back(i); return;
	}
	insert(i, lc,tl,mid);
	insert(i, rc,mid+1,tr);
}

void dijk(int *d){
	rep(v,0,2*N) stvis[v] = 0;

	rep(i,1,n+1){
		vis[i] = 0;
		if(d[i] <= n){
			pq.push({-d[i], i});
		}
	}

	while(!pq.empty()){
		auto[dist,x] = pq.top(); pq.pop();
		if(vis[x]) continue;
		vis[x] = 1;
		dist *= -1;
		// if(d==ans){dbg(x); dbg(dist);}

		int v=0,tl=1,tr=n;
		while(1){
			assert(tl<=x && x<=tr);
			if(!stvis[v]){
				stvis[v] = 1;

				for(int y : segs[v]) if(d[y] > d[x]+1){
					d[y] = d[x]+1;
					pq.push({-d[y], y});
				}
			}

			if(tl==tr) break;
			if(x<=mid){
				v=lc; tr=mid;
			}
			else{
				v=rc; tl=mid+1;
			}
		}
	}
}

void solve(){
	
	cin >> n;

	rep(i,1,n+1){
		cin >> a[i] >> b[i];

		to1[i] = ton[i] = ans[i] = INF;
		// dbg(i);
		insert(i);
	}
	// cout << nl;

	// find distance to 1
	to1[1] = 0;
	dijk(to1);
	// rep(i,1,n+1) cout << to1[i] << " ";
	// cout << nl;

	// find distance to n
	ton[n] = 0;
	dijk(ton);
	// rep(i,1,n+1) cout << ton[i] << " ";
	// cout << nl;

	// find optimal path
	rep(i,1,n+1){
		ans[i] = to1[i] + ton[i];

		// double counted your inital passport
		if(1<i && i<n) ans[i]--;

		if(a[i]==1 && b[i]==n) ans[i] = 1;
	}
	dijk(ans);
	

	int q; cin >> q;
	while(q--){
		int i; cin >> i;
		int out = ans[i];
		// if(1<i && i<n && out>1) out--;
		if(out>n) out = -1;
		cout << out << nl;
	}
	
}

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