Submission #102008

#	Time	Username	Problem	Language	Result	Execution time	Memory
102008		scanhex	Railway Trip (JOI17_railway_trip)	C++17	30 / 100	2057 ms	45736 KiB

railway_trip

#include <bits/stdc++.h>
 
using namespace std;
using nagai = long long;
#define sz(x) int((x).size())
 
const int LG=17;
const int N=1<<LG;
const int oo=0x3f3f3f3f;
int n,k,q;
int l[N];
int go[LG][N][2];
int cost[LG][N][2];
vector<int>occ[N];
 
int count_occ(int lev,int l,int r){
    return lower_bound(occ[lev].begin(),occ[lev].end(),r)-lower_bound(occ[lev].begin(),occ[lev].end(),l);
}
 
pair<int,int> mx[2*N];
void build(){
    for(int i=0;i<n;++i)
        mx[N+i]={l[i],i};
    for(int i=n;i<N;++i)
        mx[N+i]={0,0};
    for(int i=N-1;i>=0;--i)
        mx[i]=max(mx[2*i],mx[2*i+1]);
}
 
int ft(int x,int l,int r,int ql,int qx){
    if(r<=ql||mx[x].first<qx)
        return -1;
    if(r-l==1)
        return mx[x].second;
    int m=(l+r)/2;
    int ans=ft(x*2,l,m,ql,qx);
    if(ans==-1)ans=ft(x*2+1,m,r,ql,qx);
    return ans;
}
 
int lst(int x,int l,int r,int qr,int qx){
    if(l>=qr||mx[x].first<qx)
        return -1;
    if(r-l==1)
        return mx[x].second;
    int m=(l+r)/2;
    int ans=lst(x*2+1,m,r,qr,qx);
    if(ans==-1)ans=lst(x*2,l,m,qr,qx);
    return ans;
}
 
pair<int,int> getmax(int l,int r){
     l+=N;
     r+=N;
     pair<int,int> ans={-1,-1};
     while(l<r){
          if(l&1)
              ans=max(ans,mx[l++]);
          if(r&1)
              ans=max(ans,mx[--r]);
          l/=2,r/=2;
     }
     return ans;
}
 
int pref[N],suff[N];
 
int cntcalled=0;
pair<int,int> goleri(int x,int lev,int dir,int from,int mx=oo){
	if(mx<0)return {x,0};
    ++cntcalled;
    if(l[x]>=lev)return {x,0};
    if(l[go[0][x][dir]]>=lev)
        return {go[0][x][dir],cost[0][x][dir]};
    if(dir==0&&l[pref[x]]<lev)
        return {pref[x],oo};
    if(dir==1&&l[suff[x]]<lev)
        return {suff[x],oo};
    for(int i=from;i>=0;--i){
        if(l[x]+(1<<i)<=lev){
            auto p=goleri(go[i][x][dir],lev,dir,i-1,mx-cost[i][x][dir]);
            p.second+=cost[i][x][dir];
			if(l[go[i][x][dir]]>=lev)
				return p;
//          auto q=make_pair(go[i][x][1^dir],cost[i][x][1^dir]+1);
            auto q=goleri(go[i][x][1^dir],lev,dir,i-1,min(mx,p.second)-cost[i][x][1^dir]);
            q.second+=cost[i][x][1^dir];
            if(dir==0&&q.first>x||dir==1&&q.first<x)
                ++q.second,q.first=p.first;
            return {p.first,min(q.second,p.second)};
        }
    }
    return {x,oo};
    exit(239);
}
 
 
inline pair<int,int> gole(int x,int lev,int from=LG-1){
    return goleri(x,lev,0,from);
}
inline pair<int,int> gori(int x,int lev,int from=LG-1){
    return goleri(x,lev,1,from);
}
 
int d[N];
 
int stup_calc(int a,int b){
    if(b<a)
        swap(a,b);
    int ans=0;
    for(int i=a;i<=b;++i){
        if(l[i]>=l[a]||l[i]>=l[b])
            ++ans;
    }
    return ans-1;
}
struct cmp{
     bool operator()(int a,int b) const{
         if(d[a]!=d[b])
             return d[a]<d[b];
         return a<b;
     };
};
int stupid(int a,int b){
    memset(d,0x3f,sizeof d);
    d[a]=0;
    set<int,cmp>st;
    st.insert(a);
    while(st.size()){
         int x=*st.begin();
         st.erase(st.begin());
         if(x==b)
             return d[x];
         for(int y=0;y<n;++y){
             int v=stup_calc(x,y);
             if(d[x]+v<d[y]){
                  st.erase(y);
                  d[y]=d[x]+v;
                  st.insert(y);
             }
         }
    }
    assert(false);
}
 
bool st=false;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    n=100000,k=-1,q=100000;
	cin>>n>>k>>q;
    for(int i=0;i<n;++i){
		cin>>l[i];
        --l[i];
        occ[l[i]].push_back(i);
    }
    memset(cost,0,sizeof cost);
    memset(go,0,sizeof go);
    build();
    pref[0]=0;
    for(int i=1;i<n;++i)
        if(l[i]>=l[pref[i-1]])pref[i]=i;
        else pref[i]=pref[i-1];
    suff[n-1]=n-1;
    for(int i=n-2;i>=0;--i)
        if(l[i]>=l[suff[i+1]])suff[i]=i;
        else suff[i]=suff[i+1];
    for(int i=0;i<n;++i){
        if((go[0][i][0]=lst(1,0,N,i,l[i]+1))==-1)
            go[0][i][0]=i;
        else
            cost[0][i][0]=count_occ(l[i],go[0][i][0],i+1);
        if((go[0][i][1]=ft(1,0,N,i,l[i]+1))==-1)
            go[0][i][1]=i;
        else
            cost[0][i][1]=count_occ(l[i],i,go[0][i][1]);
        if(go[0][i][1]!=i&&go[0][i][0]!=i){
            cost[0][i][0]=min(cost[0][i][0],cost[0][i][1]+1);
            cost[0][i][1]=min(cost[0][i][1],cost[0][i][0]+1);
        }
    }
//  cerr<<gole(1,6,1).first<<'\n';
    for(int i=1;i<LG;++i){
        for(int j=0;j<n;++j){
            go[i][j][0]=go[i][j][1]=j;
            int lev=l[j]+(1<<i);
			if(l[j]+(1<<i-1)>=l[pref[j]])
				go[i][j][0]=go[i-1][j][0],cost[i][j][0]=cost[i-1][j][0];
			else{
				auto p=gole(j,min(lev,l[pref[j]]),i-1);
				go[i][j][0]=p.first,cost[i][j][0]=p.second;
			}
			if(l[j]+(1<<i-1)>=l[suff[j]])
				go[i][j][1]=go[i-1][j][1],cost[i][j][1]=cost[i-1][j][1];
			else{
				auto q=gori(j,min(lev,l[suff[j]]),i-1);
				go[i][j][1]=q.first,cost[i][j][1]=q.second;
			}
        }
    }
    for(int i=0;i<q;++i){
         int a,b;
		 cin>>a>>b;
         --a,--b;
         if(a>b)swap(a,b);
         int ans=b-a;
         int kek=getmax(a,b+1).first;
         vector<pair<int,int>>as={gori(a,kek)};
         vector<pair<int,int>>bs={gole(b,kek)};
         for(auto a1:as)
             for(auto b1:bs){
                 if(l[a1.first]>=kek&&l[b1.first]>=kek){
                     if(a1.first==b1.first)
                         ans=min(ans,a1.second+b1.second);
                     ans=min(ans,a1.second+b1.second+count_occ(kek,a1.first+1,b1.first)+1);
                 }
             }
         auto a1=gole(a,kek+1);
         auto b1=gori(b,kek+1);
         if(l[a1.first]>kek&&l[b1.first]>kek)
             ans=min(ans,a1.second+b1.second+1);
		 cout<<ans-1<<'\n';
    }
    return 0;
}

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