oj.uz

Submission #884706

# Submission time Handle Problem Language Result Execution time Memory
884706 2023-12-08T06:47:46 Z NotLinux Passport (JOI23_passport) C++17
100 / 100
 844 ms 232848 KB 
#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[1] = s1.extract(1);
	for(int i = 1;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[1] = s2.extract(n);
	for(int i = 1;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
	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] - 1, 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] == inf ? -1 : ans[x]) << '\n';
	}
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase = 1;//cin >> testcase;
	while(testcase--)solve();
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 77908 KB Output is correct
2 Correct 27 ms 77916 KB Output is correct
3 Correct 28 ms 77916 KB Output is correct
4 Correct 779 ms 210472 KB Output is correct
5 Correct 435 ms 148072 KB Output is correct
6 Correct 281 ms 141488 KB Output is correct
7 Correct 239 ms 177640 KB Output is correct
8 Correct 164 ms 168604 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 77916 KB Output is correct
2 Correct 27 ms 77724 KB Output is correct
3 Correct 28 ms 77908 KB Output is correct
4 Correct 27 ms 77808 KB Output is correct
5 Correct 27 ms 77904 KB Output is correct
6 Correct 27 ms 77764 KB Output is correct
7 Correct 27 ms 77904 KB Output is correct
8 Correct 27 ms 77916 KB Output is correct
9 Correct 28 ms 77904 KB Output is correct
10 Correct 28 ms 77916 KB Output is correct
11 Correct 29 ms 77932 KB Output is correct
12 Correct 27 ms 77912 KB Output is correct
13 Correct 27 ms 77916 KB Output is correct
14 Correct 27 ms 77916 KB Output is correct
15 Correct 28 ms 77908 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 77916 KB Output is correct
2 Correct 27 ms 77724 KB Output is correct
3 Correct 28 ms 77908 KB Output is correct
4 Correct 27 ms 77808 KB Output is correct
5 Correct 27 ms 77904 KB Output is correct
6 Correct 27 ms 77764 KB Output is correct
7 Correct 27 ms 77904 KB Output is correct
8 Correct 27 ms 77916 KB Output is correct
9 Correct 28 ms 77904 KB Output is correct
10 Correct 28 ms 77916 KB Output is correct
11 Correct 29 ms 77932 KB Output is correct
12 Correct 27 ms 77912 KB Output is correct
13 Correct 27 ms 77916 KB Output is correct
14 Correct 27 ms 77916 KB Output is correct
15 Correct 28 ms 77908 KB Output is correct
16 Correct 32 ms 78940 KB Output is correct
17 Correct 32 ms 78648 KB Output is correct
18 Correct 33 ms 79184 KB Output is correct
19 Correct 33 ms 79192 KB Output is correct
20 Correct 32 ms 78684 KB Output is correct
21 Correct 35 ms 78692 KB Output is correct
22 Correct 29 ms 78924 KB Output is correct
23 Correct 31 ms 78940 KB Output is correct
24 Correct 30 ms 78940 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 77916 KB Output is correct
2 Correct 27 ms 77724 KB Output is correct
3 Correct 28 ms 77908 KB Output is correct
4 Correct 27 ms 77808 KB Output is correct
5 Correct 27 ms 77904 KB Output is correct
6 Correct 27 ms 77764 KB Output is correct
7 Correct 27 ms 77904 KB Output is correct
8 Correct 27 ms 77916 KB Output is correct
9 Correct 28 ms 77904 KB Output is correct
10 Correct 28 ms 77916 KB Output is correct
11 Correct 29 ms 77932 KB Output is correct
12 Correct 27 ms 77912 KB Output is correct
13 Correct 27 ms 77916 KB Output is correct
14 Correct 27 ms 77916 KB Output is correct
15 Correct 28 ms 77908 KB Output is correct
16 Correct 32 ms 78940 KB Output is correct
17 Correct 32 ms 78648 KB Output is correct
18 Correct 33 ms 79184 KB Output is correct
19 Correct 33 ms 79192 KB Output is correct
20 Correct 32 ms 78684 KB Output is correct
21 Correct 35 ms 78692 KB Output is correct
22 Correct 29 ms 78924 KB Output is correct
23 Correct 31 ms 78940 KB Output is correct
24 Correct 30 ms 78940 KB Output is correct
25 Correct 26 ms 77904 KB Output is correct
26 Correct 28 ms 77908 KB Output is correct
27 Correct 33 ms 78928 KB Output is correct
28 Correct 31 ms 78720 KB Output is correct
29 Correct 30 ms 78612 KB Output is correct
30 Correct 31 ms 78684 KB Output is correct
31 Correct 30 ms 79192 KB Output is correct

Subtask #5
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 77908 KB Output is correct
2 Correct 27 ms 77916 KB Output is correct
3 Correct 28 ms 77916 KB Output is correct
4 Correct 779 ms 210472 KB Output is correct
5 Correct 435 ms 148072 KB Output is correct
6 Correct 281 ms 141488 KB Output is correct
7 Correct 239 ms 177640 KB Output is correct
8 Correct 164 ms 168604 KB Output is correct
9 Correct 28 ms 77916 KB Output is correct
10 Correct 27 ms 77724 KB Output is correct
11 Correct 28 ms 77908 KB Output is correct
12 Correct 27 ms 77808 KB Output is correct
13 Correct 27 ms 77904 KB Output is correct
14 Correct 27 ms 77764 KB Output is correct
15 Correct 27 ms 77904 KB Output is correct
16 Correct 27 ms 77916 KB Output is correct
17 Correct 28 ms 77904 KB Output is correct
18 Correct 28 ms 77916 KB Output is correct
19 Correct 29 ms 77932 KB Output is correct
20 Correct 27 ms 77912 KB Output is correct
21 Correct 27 ms 77916 KB Output is correct
22 Correct 27 ms 77916 KB Output is correct
23 Correct 28 ms 77908 KB Output is correct
24 Correct 32 ms 78940 KB Output is correct
25 Correct 32 ms 78648 KB Output is correct
26 Correct 33 ms 79184 KB Output is correct
27 Correct 33 ms 79192 KB Output is correct
28 Correct 32 ms 78684 KB Output is correct
29 Correct 35 ms 78692 KB Output is correct
30 Correct 29 ms 78924 KB Output is correct
31 Correct 31 ms 78940 KB Output is correct
32 Correct 30 ms 78940 KB Output is correct
33 Correct 26 ms 77904 KB Output is correct
34 Correct 28 ms 77908 KB Output is correct
35 Correct 33 ms 78928 KB Output is correct
36 Correct 31 ms 78720 KB Output is correct
37 Correct 30 ms 78612 KB Output is correct
38 Correct 31 ms 78684 KB Output is correct
39 Correct 30 ms 79192 KB Output is correct
40 Correct 844 ms 212820 KB Output is correct
41 Correct 466 ms 150520 KB Output is correct
42 Correct 557 ms 228976 KB Output is correct
43 Correct 549 ms 232848 KB Output is correct
44 Correct 308 ms 144580 KB Output is correct
45 Correct 351 ms 160184 KB Output is correct
46 Correct 164 ms 107876 KB Output is correct
47 Correct 438 ms 180420 KB Output is correct
48 Correct 434 ms 182664 KB Output is correct