oj.uz

Submission #102008

# Submission time Handle Problem Language Result Execution time Memory
102008 2019-03-21T13:25:43 Z scanhex Railway Trip (JOI17_railway_trip) C++17
30 / 100
 2000 ms 45736 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 40312 KB Output is correct
2 Correct 40 ms 40312 KB Output is correct
3 Correct 43 ms 40312 KB Output is correct
4 Correct 35 ms 40440 KB Output is correct
5 Correct 33 ms 40440 KB Output is correct
6 Correct 34 ms 40340 KB Output is correct
7 Correct 33 ms 40440 KB Output is correct
8 Correct 31 ms 40316 KB Output is correct
9 Correct 35 ms 40420 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 40440 KB Output is correct
2 Correct 138 ms 42532 KB Output is correct
3 Correct 115 ms 42464 KB Output is correct
4 Correct 128 ms 42424 KB Output is correct
5 Correct 147 ms 42460 KB Output is correct
6 Correct 164 ms 42488 KB Output is correct
7 Correct 206 ms 44280 KB Output is correct
8 Correct 131 ms 42232 KB Output is correct
9 Execution timed out 2056 ms 43256 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 332 ms 43960 KB Output is correct
2 Correct 288 ms 43896 KB Output is correct
3 Correct 313 ms 44152 KB Output is correct
4 Correct 359 ms 44044 KB Output is correct
5 Correct 323 ms 44024 KB Output is correct
6 Correct 326 ms 44024 KB Output is correct
7 Correct 306 ms 44152 KB Output is correct
8 Correct 221 ms 44056 KB Output is correct
9 Correct 233 ms 44020 KB Output is correct
10 Correct 244 ms 44020 KB Output is correct
11 Correct 290 ms 44072 KB Output is correct
12 Correct 312 ms 44020 KB Output is correct
13 Correct 284 ms 44020 KB Output is correct
14 Correct 324 ms 44024 KB Output is correct
15 Correct 364 ms 43956 KB Output is correct
16 Correct 336 ms 43888 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 688 ms 45624 KB Output is correct
2 Correct 786 ms 45736 KB Output is correct
3 Correct 563 ms 44536 KB Output is correct
4 Correct 709 ms 44840 KB Output is correct
5 Correct 245 ms 44020 KB Output is correct
6 Execution timed out 2057 ms 43384 KB Time limit exceeded
7 Halted 0 ms 0 KB -