oj.uz

Submission #411910

# Submission time Handle Problem Language Result Execution time Memory
411910 2021-05-26T08:37:37 Z alishahali1382 Railway Trip (JOI17_railway_trip) C++14
100 / 100
 788 ms 30412 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const int inf=1000000010;
const ll INF=1000000000000001000LL;
const int mod=1000000007;
const int MAXN=100010, LOG=17;

int n, m, k, u, v, x, y, t, a, b, ans;
int A[MAXN], L[MAXN], R[MAXN];
pii SP[LOG][MAXN];
int L2[LOG][MAXN], R2[LOG][MAXN];
pii seg[MAXN<<1];

pii Get(int l, int r){
	pii res=seg[0];
	for (l+=n, r+=n; l<r; l>>=1, r>>=1){
		if (l&1) res=max(res, seg[l++]);
		if (r&1) res=max(res, seg[--r]);
	}
	return res;
}
pii combine(pii i, pii j){ return {min(i.first, j.first), max(i.second, j.second)};}
int Go(int x, int y){
	if (x==y) return 0;
	if (Get(min(x, y), max(x, y)+1).first>A[y] || min(x, y)==0 || max(x, y)==n+1) return inf;
	// A[x]<=A[y]
	pii p={x, x};
	int ans=0;
	for (int i=LOG-1; ~i; i--){
		pii q=combine(SP[i][p.first], SP[i][p.second]);
		if (A[q.first]>A[y] || A[q.second]>A[y]) continue ;
		if (y<q.first || q.second<y){
			p=q;
			ans+=(1<<i);
		}
	}
//	debugp(p)
//	debug(ans)
	if (A[p.second]>A[p.first]) x=p.second;
	else if (A[p.second]<A[p.first]) x=p.first;
	else{
		if (x<y) x=p.second;
		else x=p.first;
	}
	if (x<y){
		for (int i=LOG-1; ~i; i--) if (R2[i][x]<y){
			x=R2[i][x];
			ans+=(1<<i);
		}
	}
	if (x>y){
		for (int i=LOG-1; ~i; i--) if (L2[i][x]>y){
			x=L2[i][x];
			ans+=(1<<i);
		}
	}
	return ans+1;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n>>k>>m;
	for (int i=1; i<=n; i++) cin>>A[i];
	for (int i=1; i<=n; i++) for (L[i]=i-1; L[i] && A[L[i]]<A[i]; L[i]=L[L[i]]);
	for (int i=n; i; i--) for (R[i]=i+1; R[i]<=n && A[R[i]]<A[i]; R[i]=R[R[i]]);
	for (int i=1; i<=n; i++) seg[i+n]={A[i], i};
	for (int i=n-1; i; i--) seg[i]=max(seg[i<<1], seg[i<<1 | 1]);
	
	R[n+1]=n+1;
	for (int i=0; i<=n+1; i++){
		SP[0][i]={L[i], R[i]};
		L2[0][i]=L[i];
		R2[0][i]=R[i];
	}
	for (int j=1; j<LOG; j++) for (int i=0; i<=n+1; i++){
		int x=SP[j-1][i].first, y=SP[j-1][i].second;
		SP[j][i]=combine(SP[j-1][x], SP[j-1][y]);
		L2[j][i]=L2[j-1][L2[j-1][i]];
		R2[j][i]=R2[j-1][R2[j-1][i]];
	}
	A[0]=A[n+1]=k+1;
	
//	debug(Go(2, 7))
//	debug(Go(8, 7))
//	return 0;
	
	
	while (m--){
		cin>>x>>y;
		if (x>y) swap(x, y);
		
		int mx=Get(x, y+1).second, z=mx;
		ans=Go(x, z)+Go(y, z);

		z=mx;
		for (int i=LOG-1; ~i; i--) if (R2[i][z]<=y || A[R2[i][z]]==A[mx]) z=R2[i][z];
		z=R[z];
		ans=min(ans, Go(x, z)+Go(y, z));
		
		z=mx;
		for (int i=LOG-1; ~i; i--) if (x<=L2[i][z] || A[L2[i][z]]==A[mx]) z=L2[i][z];
		z=L[z];
		ans=min(ans, Go(x, z)+Go(y, z));
		
		cout<<ans-1<<"\n";
	}
	
	return 0;
}
/*
15 15 1
15 6 14 8 1 9 13 3 5 10 3 2 10 3 15 
12 4

15 15 1
15 2 13 3 14 3 3 13 4 13 6 3 13 4 15 
6 12

*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 1 ms 588 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 38 ms 29644 KB Output is correct
3 Correct 37 ms 29664 KB Output is correct
4 Correct 31 ms 29584 KB Output is correct
5 Correct 34 ms 29636 KB Output is correct
6 Correct 32 ms 29560 KB Output is correct
7 Correct 34 ms 29548 KB Output is correct
8 Correct 48 ms 29636 KB Output is correct
9 Correct 33 ms 29536 KB Output is correct
10 Correct 38 ms 29556 KB Output is correct
11 Correct 42 ms 29652 KB Output is correct
12 Correct 31 ms 29632 KB Output is correct
13 Correct 32 ms 29560 KB Output is correct
14 Correct 34 ms 29568 KB Output is correct
15 Correct 33 ms 29648 KB Output is correct
16 Correct 33 ms 29628 KB Output is correct
17 Correct 34 ms 29636 KB Output is correct
18 Correct 33 ms 29636 KB Output is correct
19 Correct 35 ms 29632 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 561 ms 30132 KB Output is correct
2 Correct 561 ms 30048 KB Output is correct
3 Correct 559 ms 30116 KB Output is correct
4 Correct 582 ms 30076 KB Output is correct
5 Correct 557 ms 30208 KB Output is correct
6 Correct 603 ms 30092 KB Output is correct
7 Correct 554 ms 30016 KB Output is correct
8 Correct 539 ms 30196 KB Output is correct
9 Correct 740 ms 30412 KB Output is correct
10 Correct 769 ms 30216 KB Output is correct
11 Correct 781 ms 30200 KB Output is correct
12 Correct 788 ms 30352 KB Output is correct
13 Correct 762 ms 30208 KB Output is correct
14 Correct 477 ms 30076 KB Output is correct
15 Correct 491 ms 30104 KB Output is correct
16 Correct 481 ms 30020 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 29988 KB Output is correct
2 Correct 412 ms 29840 KB Output is correct
3 Correct 412 ms 30140 KB Output is correct
4 Correct 408 ms 30004 KB Output is correct
5 Correct 777 ms 30208 KB Output is correct
6 Correct 737 ms 30152 KB Output is correct
7 Correct 728 ms 30184 KB Output is correct
8 Correct 778 ms 30208 KB Output is correct
9 Correct 730 ms 30044 KB Output is correct
10 Correct 725 ms 30144 KB Output is correct
11 Correct 743 ms 30104 KB Output is correct
12 Correct 757 ms 30096 KB Output is correct
13 Correct 763 ms 30136 KB Output is correct
14 Correct 723 ms 30128 KB Output is correct
15 Correct 751 ms 30168 KB Output is correct
16 Correct 749 ms 30168 KB Output is correct
17 Correct 518 ms 30280 KB Output is correct
18 Correct 545 ms 30116 KB Output is correct
19 Correct 556 ms 30060 KB Output is correct
20 Correct 439 ms 30020 KB Output is correct
21 Correct 437 ms 29928 KB Output is correct
22 Correct 428 ms 29924 KB Output is correct
23 Correct 436 ms 29900 KB Output is correct