Submission #1066410

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066410		oscar1f	Railway Trip (JOI17_railway_trip)	C++17	100 / 100	1136 ms	326320 KiB

railway_trip

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int TAILLE_MAX=100*1000+5,INFINI=1000*1000*1000,DECA=(1<<17),MAX_INTER=900*1000+5,MAX_LOG=20;
int nbVal,typeMaxi,nbReq,nbInter;
int val[TAILLE_MAX];
vector<int> posVal[TAILLE_MAX];
set<int> plusGrand;
set<int>::iterator it;
int supVois[TAILLE_MAX][2];
int distVois[TAILLE_MAX][2];
int numEgau[TAILLE_MAX];
int arbreSom[2*DECA];
vector<pair<int,int>> interInteress;
unordered_map<int,int> corres;
int suiv[MAX_INTER][MAX_LOG][2];
int hautInter[MAX_INTER];

int hache(int deb,int fin) {
    return deb*TAILLE_MAX+fin;
}

void ajout(int pos) {
    pos+=DECA;
    while (pos>0) {
        arbreSom[pos]++;
        pos/=2;
    }
}

int calcInter(int deb,int fin) {
    if (deb==fin) {
        return arbreSom[deb];
    }
    if (deb%2==1) {
        return arbreSom[deb]+calcInter(deb+1,fin);
    }
    if (fin%2==0) {
        return arbreSom[fin]+calcInter(deb,fin-1);
    }
    return calcInter(deb/2,fin/2);
}

void calcSuiv(int deb,int fin,int diff) {
    int distGau=0,distDro=0,caseTab=corres[hache(deb,fin)]+nbInter*diff;
    hautInter[caseTab]=min(val[deb],val[fin]);
    if (diff==0) {
        distGau=1;
    }
    else if (diff==2) {
        distDro=1;
    }
    int voisGau=deb,voisDro=fin,pos,hautSuiv=min(val[deb],val[fin])+1;
    //cout<<caseTab<<" ";
    if (hautSuiv>typeMaxi) {
        //cout<<"#"<<caseTab%nbInter<<" ";
        suiv[caseTab][0][0]=caseTab;
        suiv[caseTab][0][1]=0;
    }
    else {
        pos=voisGau;
        if (val[pos]<hautSuiv) {
            voisGau=supVois[pos][0];
            distGau+=distVois[pos][0];
        }
        pos=voisDro;
        if (val[pos]<hautSuiv) {
            voisDro=supVois[pos][1];
            distDro+=distVois[pos][1];
        }
        distGau=min(distGau,distDro+1);
        distDro=min(distDro,distGau+1);
        int suivDiff,minDist=min(distGau,distDro);
        distGau-=minDist;
        distDro-=minDist;
        if (distGau==1 and distDro==0) {
            suivDiff=0;
        }
        else if (distGau==0 and distDro==0) {
            suivDiff=1;
        }
        else {
            suivDiff=2;
        }
        suiv[caseTab][0][0]=corres[hache(voisGau,voisDro)]+nbInter*suivDiff;
        suiv[caseTab][0][1]=minDist;
    }
}

pair<int,int> findInter(int pos,int hautMax) {
    if (hautInter[pos]>=hautMax) {
        return {pos,0};
    }
    int distParc=0;
    for (int i=MAX_LOG-1;i>=0;i--) {
        if (hautInter[suiv[pos][i][0]]<hautMax) {
            distParc+=suiv[pos][i][1];
            pos=suiv[pos][i][0];
        }
    }
    distParc+=suiv[pos][0][1];
    pos=suiv[pos][0][0];
    return {pos,distParc};
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>nbVal>>typeMaxi>>nbReq;
    for (int i=1;i<=nbVal;i++) {
        cin>>val[i];
        numEgau[i]=posVal[val[i]].size();
        posVal[val[i]].push_back(i);
        interInteress.push_back({i,i});
    }
    plusGrand.insert(-INFINI);
    plusGrand.insert(INFINI);
    for (int i=typeMaxi;i>=1;i--) {
        for (int j:posVal[i]) {
            it=plusGrand.lower_bound(j);
            if (abs((*it))!=INFINI) {
                supVois[j][1]=(*it);
            }
            it--;
            if (abs((*it))!=INFINI) {
                supVois[j][0]=(*it);
            }
        }
        for (int j:posVal[i]) {
            plusGrand.insert(j);
            ajout(j);
        }
        for (int j:posVal[i]) {
            if (supVois[j][0]!=0) {
                distVois[j][0]=calcInter(DECA+1,DECA+j)-calcInter(DECA+1,DECA+supVois[j][0]);
            }
            if (supVois[j][1]!=0) {
                distVois[j][1]=calcInter(DECA+1,DECA+supVois[j][1])-calcInter(DECA+1,DECA+j);
            }
            it=plusGrand.lower_bound(j);
            it++;
            if (abs((*it))!=INFINI and val[(*it)]>i) {
                interInteress.push_back({j,abs(*it)});
            }
            it--;
            it--;
            if (abs((*it))!=INFINI) {
                interInteress.push_back({abs(*it),j});
            }
        }
    }
    //cout<<interInteress.size()<<endl;
    nbInter=interInteress.size();
    for (int i=0;i<nbInter;i++) {
        //cout<<interInteress[i].first<<" "<<interInteress[i].second<<endl;
        corres[hache(interInteress[i].first,interInteress[i].second)]=i;
    }
    for (int i=0;i<nbInter;i++) {
        for (int j=0;j<3;j++) {
            calcSuiv(interInteress[i].first,interInteress[i].second,j);
        }
        //cout<<interInteress[i].first<<" "<<interInteress[i].second<<" : "<<interInteress[suiv[i][0][0]%nbInter].first<<" "<<interInteress[suiv[i][0][0]%nbInter].second<<endl;
    }
    for (int j=1;j<MAX_LOG;j++) {
        for (int i=0;i<3*nbInter;i++) {
            suiv[i][j][0]=suiv[suiv[i][j-1][0]][j-1][0];
            suiv[i][j][1]=suiv[i][j-1][1]+suiv[suiv[i][j-1][0]][j-1][1];
        }
    }
    int deb,fin,rep,hautMax,debDicho,finDicho,midDicho;
    pair<int,int> interGau,interDro;
    for (int ireq=0;ireq<nbReq;ireq++) {
        cin>>deb>>fin;
        if (deb>fin) {
            swap(deb,fin);
        }
        debDicho=max(val[deb],val[fin])+1;
        finDicho=typeMaxi+1;
        while (debDicho!=finDicho) {
            midDicho=(debDicho+finDicho)/2;
            interGau=findInter(corres[hache(deb,deb)]+nbInter,midDicho);
            interDro=findInter(corres[hache(fin,fin)]+nbInter,midDicho);
            if (interGau.first%nbInter==interDro.first%nbInter) {
                finDicho=midDicho;
            }
            else {
                debDicho=midDicho+1;
            }
        } 
        hautMax=debDicho;
        if (hautMax<=typeMaxi) {
            interGau=findInter(corres[hache(deb,deb)]+nbInter,hautMax);
            interDro=findInter(corres[hache(fin,fin)]+nbInter,hautMax);
            rep=interGau.second+interDro.second+min((interGau.first/nbInter==0)+(interDro.first/nbInter==0),
                                                  (interGau.first/nbInter==2)+(interDro.first/nbInter==2));
        }
        else {
            rep=INFINI;
        }
        //cout<<"!"<<hautMax-1<<" "<<rep<<endl;
        interGau=findInter(corres[hache(deb,deb)]+nbInter,hautMax-1);
        interDro=findInter(corres[hache(fin,fin)]+nbInter,hautMax-1);
        rep=min(rep,interGau.second+(interGau.first/nbInter==2)+interDro.second+(interDro.first/nbInter==0)+
                    numEgau[interInteress[interDro.first%nbInter].first]-numEgau[interInteress[interGau.first%nbInter].second]);
        /*if (rep<=0) {
            cout<<deb<<" "<<fin<<endl;
        }*/
        cout<<rep-1<<"\n";
    }
    //cout<<endl;
    return 0;
}
 

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