Submission #1065148

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065148		oscar1f	Railway Trip (JOI17_railway_trip)	C++17	45 / 100	2063 ms	17212 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);
int nbVal,typeMaxi,nbReq;
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];
int voisGau[TAILLE_MAX][2],voisDro[TAILLE_MAX][2];
int distGau[TAILLE_MAX][2],distDro[TAILLE_MAX][2];

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 calcSup(int deb,int tab) {
    distGau[1][tab]=0;
    distDro[1][tab]=0;
    voisGau[1][tab]=deb;
    voisDro[1][tab]=deb;
    int pos;
    for (int i=2;i<=typeMaxi;i++) {
        pos=voisGau[i-1][tab];
        if (val[pos]<i) {
            voisGau[i][tab]=supVois[pos][0];
            distGau[i][tab]=distGau[i-1][tab]+distVois[pos][0];
        }
        else {
            voisGau[i][tab]=pos;
            distGau[i][tab]=distGau[i-1][tab];
        }
        pos=voisDro[i-1][tab];
        if (val[pos]<i) {
            voisDro[i][tab]=supVois[pos][1];
            distDro[i][tab]=distDro[i-1][tab]+distVois[pos][1];
        }
        else {
            voisDro[i][tab]=pos;
            distDro[i][tab]=distDro[i-1][tab];
        }
        distGau[i][tab]=min(distGau[i][tab],distDro[i][tab]+1);
        distDro[i][tab]=min(distDro[i][tab],distGau[i][tab]+1);
    }
    /*for (int i=1;i<=typeMaxi;i++) {
        cout<<i<<"   "<<voisGau[i][tab]<<" "<<distGau[i][tab]<<"    "<<voisDro[i][tab]<<" "<<distDro[i][tab]<<endl;
    }
    cout<<endl;*/
}

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);
    }
    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);
            }
        }
    }
    int deb,fin,rep,hautMax;
    for (int ireq=0;ireq<nbReq;ireq++) {
        cin>>deb>>fin;
        if (deb>fin) {
            swap(deb,fin);
        }
        calcSup(deb,0);
        calcSup(fin,1);
        hautMax=1;
        while (hautMax<=typeMaxi and voisDro[hautMax][0]<=voisGau[hautMax][1]) {
            hautMax++;
        }
        if (hautMax<=typeMaxi) {
            rep=min(distGau[hautMax][0]+distGau[hautMax][1],distDro[hautMax][0]+distDro[hautMax][1]);
        }
        else {
            rep=INFINI;
        }
        hautMax--;
        //cout<<"!"<<hautMax<<endl;
        rep=min(rep,distDro[hautMax][0]+distGau[hautMax][1]+numEgau[voisGau[hautMax][1]]-numEgau[voisDro[hautMax][0]]);
        cout<<rep-1<<"\n";
    }
    //cout<<endl;
    return 0;
}
 

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