Submission #203006

#	Time	Username	Problem	Language	Result	Execution time	Memory
203006		gs18115	Railway Trip (JOI17_railway_trip)	C++14	100 / 100	432 ms	111096 KiB

railway_trip

#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define semicolon ;
#define ryan bear
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18+7;
struct seg
{
    pi t[400010];
    void si(int n,int s,int e,int x,int p)
    {
        if(s==e)
        {
            t[n]=pi(p,x);
            return;
        }
        int m=(s+e)/2;
        if(x>m)
            si(n*2+1,m+1,e,x,p);
        else
            si(n*2,s,m,x,p);
        t[n]=max(t[n*2],t[n*2+1]);
        return;
    }
    pi sq(int n,int s,int e,int S,int E)
    {
        if(s>E||S>e)
            return pi(-inf,0);
        if(S<=s&&e<=E)
            return t[n];
        int m=(s+e)/2;
        return max(sq(n*2,s,m,S,E),sq(n*2+1,m+1,e,S,E));
    }
}st;
int tct=2;
int dp[200010];
int spd[200010][20][2][2];
int spa[200010][20],kth[200010];
inline void app(pi&x,int y[2][2])
{
    pi t=x;
    x.fi=min(t.fi+y[0][0],t.se+y[1][0]);
    x.se=min(t.fi+y[0][1],t.se+y[1][1]);
    return;
}
inline void merge(int r[2][2],int x[2][2],int y[2][2])
{
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            r[i][j]=min(x[i][0]+y[0][j],x[i][1]+y[1][j]);
    return;
}
int lcq(int x,int y,bool rr)
{
    pi ld(0,1);
    pi rd(0,1);
    if(rr)
        rd=pi(1,0);
    if(dp[x]<dp[y])
        swap(x,y),swap(ld,rd);
    for(int i=0;i<20;i++)
        if((dp[x]-dp[y])>>i&1)
            app(ld,spd[x][i]),x=spa[x][i];
    if(x==y)
        return 0;
    for(int i=20;i-->0;)
        if(spa[x][i]!=spa[y][i])
            app(ld,spd[x][i]),app(rd,spd[y][i]),x=spa[x][i],y=spa[y][i];
    if(kth[x]>kth[y])
        swap(x,y),swap(ld,rd);
    return min(ld.se+rd.fi+kth[y]-kth[x]-1,ld.fi+rd.se+spd[x][0][0][0]+spd[y][0][1][0])-1;
}
vector<int>adj[200010];
int node[100010];
int n,k,q;
void maketree(int n,int s,int e)
{
    if(s>e-2)
    {
        node[s]=n;
        return;
    }
    pi t=st.sq(1,1,::n,s+1,e-1);
    vector<int>v;
    vector<pi>itv;
    v.eb(t.se);
    while(v.back()>s+1)
    {
        pi t2=st.sq(1,1,::n,s+1,v.back()-1);
        if(t2.fi!=t.fi)
            break;
        v.eb(t2.se);
    }
    reverse(all(v));
    itv.eb(s,v[0]);
    for(int i=1;i<(int)v.size();i++)
        itv.eb(v[i-1],v[i]);
    itv.eb(v.back(),e);
    int sz=(int)itv.size();
    for(int i=0;i<sz;i++)
    {
        int t=tct++;
        adj[n].eb(t);
        kth[t]=i;
        spa[t][0]=n;
        dp[t]=dp[n]+1;
        for(int j=0;j<2;j++)
        {
            spd[t][0][j][0]=i+j,spd[t][0][j][1]=sz-i-j;
            for(int k=0;k<2;k++)
                spd[t][0][j][k]=min(spd[t][0][j][k],spd[t][0][j][k^1]+1);
        }
    }
    for(int i=0;i<sz;i++)
        maketree(adj[n][i],itv[i].fi,itv[i].se);
    return;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>k>>q;
    if(n<3)
    {
        for(int i=0;i<q;i++)
            cout<<"0\n";
        cout.flush();
        return 0;
    }
    for(int i=0;i++<n;)
    {
        int t;
        cin>>t;
        st.si(1,1,n,i,t);
    }
    maketree(1,1,n);
    if(st.sq(1,1,n,2,n-1).fi==k)
        for(int k=0;k<(int)adj[1].size();k++)
            for(int i=0;i<2;i++)
                spd[adj[1][k]][0][i][0]=k+i,spd[adj[1][k]][0][i][1]=(int)adj[1].size()-k-i;
    for(int i=0;i<19;i++)
        for(int j=1;j<tct;j++)
            spa[j][i+1]=spa[spa[j][i]][i],merge(spd[j][i+1],spd[j][i],spd[spa[j][i]][i]);
    while(q-->0)
    {
        int l,r;
        cin>>l>>r;
        if(l>r)
            swap(l,r);
        if(r==n)
            cout<<lcq(node[l],node[r-1],1);
        else
            cout<<lcq(node[l],node[r],0);
        cout<<'\n';
    }
    cout.flush();
    return 0;
}

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