oj.uz

Submission #883837

# Submission time Handle Problem Language Result Execution time Memory
883837 2023-12-06T07:43:32 Z vjudge1 Passport (JOI23_passport) C++17
0 / 100
 1791 ms 52796 KB 
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 7;
const int M = 30;
struct SEGTMAX{//point update , range min query
	vector < int > tree;
	int sz;
	SEGTMAX(int x){
		sz = x+3;
		tree.assign(4*sz,-inf);
	}
	void _update(int ind , int l , int r , int qp , int qv){
		if(l == r){
			tree[ind] = qv;
			return;
		}
		int mid = (l+r)/2;
		if(mid >= qp)_update(ind*2,l,mid,qp,qv);
		else _update(ind*2+1,mid+1,r,qp,qv);
		tree[ind] = max(tree[ind*2] , tree[ind*2+1]);
	}
	void update(int p ,int v){
		_update(1,1,sz,p,v);
	}
	int _query(int ind , int l , int r , int ql , int qr){
		if(l >= ql and r <= qr)return tree[ind];
		else if(l > qr or r < ql)return -inf;
		int mid = (l+r)/2;
		return max(_query(ind*2,l,mid,ql,qr) , _query(ind*2+1,mid+1,r,ql,qr));
	}
	int query(int l , int r){
		if(l > r)return -inf;
		return _query(1,1,sz,l,r);
	}
};
struct SEGTMIN{//point update , range min query
	vector < int > tree;
	int sz;
	SEGTMIN(int x){
		sz = x+3;
		tree.assign(4*sz,inf);
	}
	void _update(int ind , int l , int r , int qp , int qv){
		if(l == r){
			tree[ind] = qv;
			return;
		}
		int mid = (l+r)/2;
		if(mid >= qp)_update(ind*2,l,mid,qp,qv);
		else _update(ind*2+1,mid+1,r,qp,qv);
		tree[ind] = min(tree[ind*2] , tree[ind*2+1]);
	}
	void update(int p ,int v){
		_update(1,1,sz,p,v);
	}
	int _query(int ind , int l , int r , int ql , int qr){
		if(l >= ql and r <= qr)return tree[ind];
		else if(l > qr or r < ql)return inf;
		int mid = (l+r)/2;
		return min(_query(ind*2,l,mid,ql,qr) , _query(ind*2+1,mid+1,r,ql,qr));
	}
	int query(int l , int r){
		if(l > r)return inf;
		return _query(1,1,sz,l,r);
	}
};
void solve(){
	int n;
	cin >> n;
	int liftmin[n+1][M] , liftmax[n+1][M];
	for(int i = 1;i<=n;i++){
		cin >> liftmin[i][0] >> liftmax[i][0];
	}
	for(int j = 1;j<M;j++){
		SEGTMIN segtmin(n);
		SEGTMAX segtmax(n);
		for(int i = 1;i<=n;i++){
			segtmin.update(i,liftmin[i][j-1]);
			segtmax.update(i,liftmax[i][j-1]);
		}
		//cout << "liftmin "  << j-1 << " : ";for(int i = 1;i<=n;i++)cout << liftmin[i][j-1] << " ";cout << endl;
		//cout << "liftmax "  << j-1 << " : ";for(int i = 1;i<=n;i++)cout << liftmax[i][j-1] << " ";cout << endl;
		for(int i = 1;i<=n;i++){
			liftmin[i][j] = segtmin.query(liftmin[i][j-1] , liftmax[i][j-1]);
			liftmax[i][j] = segtmax.query(liftmin[i][j-1] , liftmax[i][j-1]);
		}
	}
	int q;
	cin >> q;
	while(q--){
		int x;
		cin >> x;
		if(liftmin[x][M-1] != 1 or liftmax[x][M-1] != n){
			cout << -1 << '\n';
			continue;
		}
		int ansmin = 0 , ansmax = 0 , tempx = x;
		for(int i = M-1;i>=0;i--){
			if(liftmin[x][i] != 1){
				ansmin += (1ll << i);
				x = liftmin[x][i];
			}
		}
		if(x != 1)ansmin++;
		x = tempx;
		for(int i = M-1;i>=0;i--){
			if(liftmax[x][i] != n){
				ansmax += (1ll << i);
				x = liftmax[x][i];
			}
		}
		if(x != n)ansmax++;
		cout << max(ansmin , ansmax) << '\n';
	}
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase = 1;//cin >> testcase;
	while(testcase--)solve();
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 1791 ms 52796 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 1791 ms 52796 KB Output isn't correct
5 Halted 0 ms 0 KB -