oj.uz

Submission #116527

# Submission time Handle Problem Language Result Execution time Memory
116527 2019-06-12T17:22:07 Z shayan_p Railway Trip (JOI17_railway_trip) C++14
100 / 100
 374 ms 19664 KB 
// High above the clouds there is a rainbow...

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int maxn=1e5+10;

int a[maxn],bef[maxn],aft[maxn],n;
pii sp[20][maxn];

pii NXT(pii p,int i){
    pii ans;
    ans.F= min( sp[i][p.F].F, sp[i][p.S].F );
    ans.S= max( sp[i][p.F].S, sp[i][p.S].S );
    return ans;
}

pair<int,pii> f(int pos,int l,int r){
    pair<int,pii> ans={0,{pos,pos}};
    for(int i=19;i>=0;i--){
	pii p=NXT(ans.S,i);
	if(l<p.F && p.S<r) ans.F+=(1<<i), ans.S=p;
    }
    return ans;
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);

    int k,q;cin>>n>>k>>q;

    for(int i=0;i<n;i++){
	cin>>a[i], --a[i];
	a[i]=min(a[i],k-1);
    }
    
    for(int i=0;i<n;i++){
	bef[i]=i-1;
	while(bef[i]>=0 && a[bef[i]]<a[i])
	    bef[i]=bef[bef[i]];
    }
    for(int i=n-1;i>=0;i--){
	aft[i]=i+1;
	while(aft[i]<n && a[aft[i]]<a[i])
	    aft[i]=aft[aft[i]];
    }
    bef[0]=0, aft[n-1]=n-1;
    
    for(int i=0;i<n;i++){
	sp[0][i]={bef[i],aft[i]};
    }
    for(int i=1;i<20;i++){
	for(int j=0;j<n;j++){
	    sp[i][j]= NXT(sp[i-1][j],i-1);
	}
    }
    
    while(q--){
	int A,B; cin>>A>>B; --A,--B;
	if(A>B) swap(A,B);
	pair<int,pii> aa=f(A,-1,B);
	pair<int,pii> bb=f(B,aa.S.S,n);
	cout<<aa.F+bb.F<<"\n";
    }
    return 0;
}
// Deathly mistakes:
//  * Read the problem curfully.
//  * Check maxn.
//  * Overflows.

Subtask #1
5.0 / 5.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 25 ms 17120 KB Output is correct
3 Correct 25 ms 17120 KB Output is correct
4 Correct 25 ms 17124 KB Output is correct
5 Correct 25 ms 17144 KB Output is correct
6 Correct 27 ms 17148 KB Output is correct
7 Correct 27 ms 17152 KB Output is correct
8 Correct 23 ms 17272 KB Output is correct
9 Correct 26 ms 17152 KB Output is correct
10 Correct 25 ms 17144 KB Output is correct
11 Correct 27 ms 17144 KB Output is correct
12 Correct 27 ms 17144 KB Output is correct
13 Correct 26 ms 17152 KB Output is correct
14 Correct 27 ms 17152 KB Output is correct
15 Correct 27 ms 17144 KB Output is correct
16 Correct 31 ms 17280 KB Output is correct
17 Correct 28 ms 17116 KB Output is correct
18 Correct 27 ms 17152 KB Output is correct
19 Correct 26 ms 17144 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 17632 KB Output is correct
2 Correct 223 ms 17840 KB Output is correct
3 Correct 209 ms 17656 KB Output is correct
4 Correct 202 ms 17656 KB Output is correct
5 Correct 374 ms 17656 KB Output is correct
6 Correct 186 ms 17680 KB Output is correct
7 Correct 222 ms 17656 KB Output is correct
8 Correct 246 ms 18140 KB Output is correct
9 Correct 317 ms 19192 KB Output is correct
10 Correct 324 ms 19192 KB Output is correct
11 Correct 315 ms 19192 KB Output is correct
12 Correct 344 ms 19232 KB Output is correct
13 Correct 327 ms 19188 KB Output is correct
14 Correct 268 ms 19084 KB Output is correct
15 Correct 205 ms 19064 KB Output is correct
16 Correct 185 ms 19064 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 17516 KB Output is correct
2 Correct 137 ms 17400 KB Output is correct
3 Correct 143 ms 17400 KB Output is correct
4 Correct 144 ms 17400 KB Output is correct
5 Correct 311 ms 18296 KB Output is correct
6 Correct 218 ms 19600 KB Output is correct
7 Correct 252 ms 19664 KB Output is correct
8 Correct 269 ms 19320 KB Output is correct
9 Correct 260 ms 19448 KB Output is correct
10 Correct 246 ms 19448 KB Output is correct
11 Correct 256 ms 19320 KB Output is correct
12 Correct 224 ms 19448 KB Output is correct
13 Correct 221 ms 19448 KB Output is correct
14 Correct 275 ms 19448 KB Output is correct
15 Correct 240 ms 19448 KB Output is correct
16 Correct 312 ms 19448 KB Output is correct
17 Correct 232 ms 19448 KB Output is correct
18 Correct 230 ms 19576 KB Output is correct
19 Correct 215 ms 19448 KB Output is correct
20 Correct 161 ms 19372 KB Output is correct
21 Correct 156 ms 19336 KB Output is correct
22 Correct 160 ms 19192 KB Output is correct
23 Correct 155 ms 19288 KB Output is correct