oj.uz

Submission #116686

# Submission time Handle Problem Language Result Execution time Memory
116686 2019-06-13T14:32:08 Z jangwonyoung Railway Trip (JOI17_railway_trip) C++14
0 / 100
 1910 ms 17740 KB 
#include<bits/stdc++.h>
using namespace std;
const int lg=17;
typedef pair<int,int> pii;
int n,k,q;
int a[100001];
int l[100001],r[100001];
int sl[18][100001],sr[18][100001];
int find(int id,int val){
	if(val==id) return 0;
	int x=0;
	int bl=id,br=id,nl,nr;
	for(int i=lg; i>=0 ;i--){
		x|=(1<<i);
		nl=min(sl[i][bl],sl[i][br]);
		nr=max(sr[i][bl],sr[i][br]);
		if(nl<=val && val<=nr) x^=(1<<i);
		else bl=nl,br=nr;
	}
	x++;
	nl=min(sl[0][bl],sl[0][br]);
	nr=max(sr[0][bl],sr[0][br]);
	if(nl==val || nr==val) return x;
	else return 1e9;
}
int main(){
	ios::sync_with_stdio(false);
	cin >> n >> k >> q;
	for(int i=1; i<=n ;i++) cin >> a[i];
	stack<int>s;
	for(int i=1; i<=n ;i++){
		while(!s.empty() && a[s.top()]<a[i]) s.pop();
		if(!s.empty()) l[i]=s.top();
		else l[i]=i;
		s.push(i);
	}
	while(!s.empty()) s.pop();
	for(int i=n; i>=1 ;i--){
		while(!s.empty() && a[s.top()]<a[i]) s.pop();
		if(!s.empty()) r[i]=s.top();
		else r[i]=i;
		s.push(i);
	}
	for(int i=1; i<=n ;i++){
		sl[0][i]=l[i];sr[0][i]=r[i];
	}
	for(int j=1; j<=lg ;j++){
		for(int i=1; i<=n ;i++){
			sl[j][i]=min(sl[j-1][sl[j-1][i]],sl[j-1][sr[j-1][i]]);
			sr[j][i]=max(sr[j-1][sl[j-1][i]],sr[j-1][sr[j-1][i]]);
		}
	}
	for(int i=1; i<=q ;i++){
		int u,v;cin >> u >> v;
		if(u>v) swap(u,v);
		if(l[v]==u || r[u]==v){
			cout << "0\n";
			continue;
		}
		if(a[u]>a[v]) swap(u,v);
		int x=0,y,ans=1e9;
		int bl=u,br=u,nl,nr;
		for(int j=lg; j>=0 ;j--){
			x|=(1<<j);
			nl=min(sl[j][bl],sl[j][br]);
			nr=max(sr[j][bl],sr[j][br]);
			y=find(v,nl);
			if(y==1e9) bl=nl,br=nr;
			else x^=(1<<j);
		}
		x++;
		nl=min(sl[0][bl],sl[0][br]);
		nr=max(sr[0][bl],sr[0][br]);
		y=find(v,nl);
		ans=min(ans,x+y);
		x=0,bl=u,br=u;
		for(int j=lg; j>=0 ;j--){
			x|=(1<<j);
			nl=min(sl[j][bl],sl[j][br]);
			nr=max(sr[j][bl],sr[j][br]);
			y=find(v,nr);
			if(y==1e9) bl=nl,br=nr;
			else x^=(1<<j);
		}
		x++;
		nl=min(sl[0][bl],sl[0][br]);
		nr=max(sr[0][bl],sr[0][br]);
		y=find(v,nr);
		ans=min(ans,x+y);
		cout << ans-1 << '\n';
	}
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 26 ms 15608 KB Output is correct
3 Correct 26 ms 15616 KB Output is correct
4 Correct 27 ms 15616 KB Output is correct
5 Correct 26 ms 15616 KB Output is correct
6 Correct 27 ms 15736 KB Output is correct
7 Correct 29 ms 15564 KB Output is correct
8 Correct 24 ms 16020 KB Output is correct
9 Correct 30 ms 15864 KB Output is correct
10 Correct 27 ms 16264 KB Output is correct
11 Incorrect 30 ms 16376 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1668 ms 16352 KB Output is correct
2 Correct 1910 ms 17732 KB Output is correct
3 Correct 1656 ms 17740 KB Output is correct
4 Correct 1647 ms 17716 KB Output is correct
5 Correct 1651 ms 17656 KB Output is correct
6 Correct 1568 ms 17652 KB Output is correct
7 Incorrect 1478 ms 17724 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 769 ms 16036 KB Output isn't correct
2 Halted 0 ms 0 KB -