oj.uz

Submission #127683

# Submission time Handle Problem Language Result Execution time Memory
127683 2019-07-09T23:41:23 Z Utaha Railway Trip (JOI17_railway_trip) C++14
20 / 100
 2000 ms 9328 KB 
/*input
15 5 15
5
4
1
2
3
1
1
2
4
5
4
1
5
3
5
8 1
11 1
5 3
6 11
9 12
15 14
15 2
3 12
2 1
4 8
15 5
12 6
1 13
13 8
14 9
*/
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define F first
#define S second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define pb emplace_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
    out<<'('<<P.F<<','<<P.S<<')';
    return out;
}

//}}}
const ll maxn=100005;
const ll maxlg=__lg(maxn)+2;
const ll INF64=8000000000000000000LL;
const int INF=0x3f3f3f3f;
const ll MOD=ll(1e9+7);
const ld PI=acos(-1);
const ld eps=1e-9;
//const ll p=880301;
//const ll P=31;

ll mypow(ll a,ll b){
    ll res=1LL;
    while(b){
        if(b&1) res=res*a%MOD;
        a=a*a%MOD;
        
        b>>=1;
    }
    return res;
}

int n;
int a[maxn];

vector<int> edge[maxn];
vector<pii> st;

vector<int> q;
int pt=0;
int d[maxn];
int bfs(int u,int v){
    REP(i,n) d[i]=-1;
    q.clear();
    pt=0;
    q.pb(u);
    d[u]=0;
    while(pt<SZ(q)){
        int cur=q[pt++];
        for(int nxt:edge[cur]) if(d[nxt]==-1){
            d[nxt]=d[cur]+1;
            q.pb(nxt);
        }
    }
    return d[v];
}

int main(){
    IOS;
    int k,q;
    cin>>n>>k>>q;
    REP(i,n) cin>>a[i];
    REP(i,n){
        while(SZ(st)&&a[i]>st.back().F) st.pop_back();
        if(SZ(st)){
            edge[i].pb(st.back().S);
            edge[st.back().S].pb(i);
            // cout<<i<<' '<<st.back().S<<'\n';
        }
        st.pb(a[i],i);
    }
    st.clear();
    for(int i=n-1;i>=0;i--){
        while(SZ(st)&&a[i]>st.back().F) st.pop_back();
        if(SZ(st)){
            edge[i].pb(st.back().S);
            edge[st.back().S].pb(i);
        }
        st.pb(a[i],i);
    }

    REP(i,q){
        int u,v;
        cin>>u>>v;
        u--;v--;
        cout<<bfs(u,v)-1<<'\n';
    }

    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2680 KB Output is correct
2 Correct 225 ms 8820 KB Output is correct
3 Correct 225 ms 8648 KB Output is correct
4 Correct 236 ms 8692 KB Output is correct
5 Correct 245 ms 8744 KB Output is correct
6 Correct 264 ms 8928 KB Output is correct
7 Correct 255 ms 9076 KB Output is correct
8 Correct 121 ms 8556 KB Output is correct
9 Correct 121 ms 9200 KB Output is correct
10 Correct 121 ms 8940 KB Output is correct
11 Correct 224 ms 9324 KB Output is correct
12 Correct 214 ms 9328 KB Output is correct
13 Correct 214 ms 9328 KB Output is correct
14 Correct 222 ms 9328 KB Output is correct
15 Correct 212 ms 9328 KB Output is correct
16 Correct 212 ms 9324 KB Output is correct
17 Correct 241 ms 9076 KB Output is correct
18 Correct 241 ms 9076 KB Output is correct
19 Correct 137 ms 8436 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2059 ms 8440 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2067 ms 9204 KB Time limit exceeded
2 Halted 0 ms 0 KB -