Submission #1266404

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266404		uzukishinobu	Railway Trip (JOI17_railway_trip)	C++20	100 / 100	149 ms	35280 KiB

railway_trip

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,b,c;
int z[1000005];
int prv[100005][21];
int nxt[100005][21];

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a >> b >> c;
    for (int i=1;i<=a;i++){
         cin >> z[i];
    }
    stack<int> st;
    for (int i=1;i<=a;i++){
         while (st.size() && z[st.top()]<z[i]){
                st.pop();
         }
         if (st.size()){
             prv[i][0]=st.top();
         }else{
             prv[i][0]=1;
         }
         st.push(i);
    }
    while (st.size()){
         st.pop();
    }
    for (int i=a;i>=1;i--){
         while (st.size() && z[st.top()]<z[i]){
                st.pop();
         }
         if (st.size()){
             nxt[i][0]=st.top();
         }else{
             nxt[i][0]=a;
         }
         st.push(i);
    }
    for (int j=1;j<=20;j++){
         for (int i=1;i<=a;i++){
              int u=prv[i][j-1];
              int v=nxt[i][j-1];
              prv[i][j]=min(prv[u][j-1],prv[v][j-1]);
              nxt[i][j]=max(nxt[u][j-1],nxt[v][j-1]);
         }
    }

    while (c--){
         int x,y;
         cin >> x >> y;
         if (x>y){
            swap(x,y);
         }
         int nl=x,nr=x;
         int res=0;
         for (int i=20;i>=0;i--){
              if (max(nxt[nl][i],nxt[nr][i])<y){
                  res+=1<<i;
                  int u=nl,v=nr;
                  nl=min(prv[u][i],prv[v][i]);
                  nr=max(nxt[v][i],nxt[u][i]);
              }
         }
//         cout << res << " ";
         int p=nr;
         nl=y,nr=y;
         for (int i=20;i>=0;i--){
              if (min(prv[nl][i],prv[nr][i])>p){
                  res+=1<<i;
                  int u=nl,v=nr;
                  nl=min(prv[u][i],prv[v][i]);
                  nr=max(nxt[u][i],nxt[v][i]);
              }
         }
         cout << res << "\n";
    }
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 25 / 25
• Subtask 4: 55 / 55