oj.uz

Submission #376954

# Submission time Handle Problem Language Result Execution time Memory
376954 2021-03-12T10:58:38 Z YJU Railway Trip (JOI17_railway_trip) C++14
100 / 100
 366 ms 51564 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector,Ofast")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=4e5+5;
const ld pi=acos(-1);
const ll INF=(1LL<<60);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()

set<ll> s;
ll n,m,q,u[N];
vector<ll> in[N];
ll r[N][20],l[N][20];

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>m>>q;
	REP1(i,n){cin>>u[i];in[u[i]].pb(i);} 
	
	REP(j,20)r[n][j]=n,l[1][j]=1;
	for(int c=m;c>=1;c--){
		for(auto j:in[c]){
			s.insert(j);
		}
		for(auto j:in[c]){
			r[j][0]=(s.lwb(j+1)==s.end()?n:*s.lwb(j+1));
			l[j][0]=(s.lwb(j)==s.begin()?1:*prev(s.lwb(j)));
		}
	}
	for(int j=1;j<20;j++){
		REP1(i,n){
			r[i][j]=max(r[r[i][j-1]][j-1],r[l[i][j-1]][j-1]);
			l[i][j]=min(l[l[i][j-1]][j-1],l[r[i][j-1]][j-1]);
		}
	}
	while(q--){
		ll ans=0,a,b;
		cin>>a>>b;
		if(a>b)swap(a,b);
		ll L,R;
		L=R=a;
		for(int p=18;p>=0;p--){
			if(max(r[L][p],r[R][p])<b){
				ll TL=L,TR=R;
				ans+=(1<<p);
				L=min(l[TL][p],l[TR][p]),R=max(r[TR][p],r[TL][p]);
			}
		}
		ll mid=R;
		L=R=b;
		for(int p=18;p>=0;p--){
			if(min(l[L][p],l[R][p])>mid){
				ll TL=L,TR=R;
				ans+=(1<<p);
				L=min(l[TL][p],l[TR][p]),R=max(r[TR][p],r[TL][p]);
			}
		}
		cout<<ans<<"\n";
	}
	return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 10092 KB Output is correct
2 Correct 132 ms 47816 KB Output is correct
3 Correct 140 ms 47852 KB Output is correct
4 Correct 146 ms 47724 KB Output is correct
5 Correct 152 ms 47852 KB Output is correct
6 Correct 172 ms 48128 KB Output is correct
7 Correct 190 ms 49388 KB Output is correct
8 Correct 141 ms 47464 KB Output is correct
9 Correct 159 ms 48748 KB Output is correct
10 Correct 145 ms 48228 KB Output is correct
11 Correct 165 ms 48748 KB Output is correct
12 Correct 168 ms 48620 KB Output is correct
13 Correct 154 ms 48444 KB Output is correct
14 Correct 162 ms 48748 KB Output is correct
15 Correct 163 ms 48744 KB Output is correct
16 Correct 170 ms 48492 KB Output is correct
17 Correct 129 ms 48108 KB Output is correct
18 Correct 124 ms 48108 KB Output is correct
19 Correct 139 ms 50028 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 49260 KB Output is correct
2 Correct 242 ms 49516 KB Output is correct
3 Correct 270 ms 49388 KB Output is correct
4 Correct 246 ms 49388 KB Output is correct
5 Correct 275 ms 49516 KB Output is correct
6 Correct 239 ms 49388 KB Output is correct
7 Correct 237 ms 49576 KB Output is correct
8 Correct 285 ms 49200 KB Output is correct
9 Correct 347 ms 49256 KB Output is correct
10 Correct 353 ms 49384 KB Output is correct
11 Correct 352 ms 49468 KB Output is correct
12 Correct 339 ms 49256 KB Output is correct
13 Correct 355 ms 49512 KB Output is correct
14 Correct 324 ms 49256 KB Output is correct
15 Correct 255 ms 49140 KB Output is correct
16 Correct 240 ms 49128 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 271 ms 50796 KB Output is correct
2 Correct 278 ms 50796 KB Output is correct
3 Correct 269 ms 49772 KB Output is correct
4 Correct 267 ms 50228 KB Output is correct
5 Correct 351 ms 49256 KB Output is correct
6 Correct 331 ms 50412 KB Output is correct
7 Correct 321 ms 50540 KB Output is correct
8 Correct 325 ms 50020 KB Output is correct
9 Correct 315 ms 50412 KB Output is correct
10 Correct 337 ms 50376 KB Output is correct
11 Correct 300 ms 50160 KB Output is correct
12 Correct 312 ms 50412 KB Output is correct
13 Correct 321 ms 50272 KB Output is correct
14 Correct 317 ms 50668 KB Output is correct
15 Correct 329 ms 51180 KB Output is correct
16 Correct 366 ms 51564 KB Output is correct
17 Correct 300 ms 50412 KB Output is correct
18 Correct 312 ms 50668 KB Output is correct
19 Correct 313 ms 50540 KB Output is correct
20 Correct 289 ms 50284 KB Output is correct
21 Correct 214 ms 49772 KB Output is correct
22 Correct 200 ms 49516 KB Output is correct
23 Correct 208 ms 51436 KB Output is correct