oj.uz

Submission #1066410

# Submission time Handle Problem Language Result Execution time Memory
1066410 2024-08-19T20:46:07 Z oscar1f Railway Trip (JOI17_railway_trip) C++17
100 / 100
 1136 ms 326320 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 2 ms 10656 KB Output is correct
3 Correct 2 ms 10840 KB Output is correct
4 Correct 1 ms 10844 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 1 ms 10588 KB Output is correct
7 Correct 2 ms 10588 KB Output is correct
8 Correct 1 ms 10588 KB Output is correct
9 Correct 2 ms 10588 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 13148 KB Output is correct
2 Correct 341 ms 295080 KB Output is correct
3 Correct 337 ms 305960 KB Output is correct
4 Correct 379 ms 314796 KB Output is correct
5 Correct 402 ms 318772 KB Output is correct
6 Correct 418 ms 322876 KB Output is correct
7 Correct 414 ms 322988 KB Output is correct
8 Correct 207 ms 222384 KB Output is correct
9 Correct 266 ms 257084 KB Output is correct
10 Correct 234 ms 243028 KB Output is correct
11 Correct 297 ms 263860 KB Output is correct
12 Correct 290 ms 263860 KB Output is correct
13 Correct 309 ms 263468 KB Output is correct
14 Correct 287 ms 263608 KB Output is correct
15 Correct 292 ms 263776 KB Output is correct
16 Correct 299 ms 263912 KB Output is correct
17 Correct 355 ms 321572 KB Output is correct
18 Correct 374 ms 322092 KB Output is correct
19 Correct 358 ms 323504 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 455 ms 301872 KB Output is correct
2 Correct 456 ms 297168 KB Output is correct
3 Correct 493 ms 302916 KB Output is correct
4 Correct 463 ms 304560 KB Output is correct
5 Correct 504 ms 305172 KB Output is correct
6 Correct 471 ms 306968 KB Output is correct
7 Correct 477 ms 308268 KB Output is correct
8 Correct 325 ms 249008 KB Output is correct
9 Correct 293 ms 224824 KB Output is correct
10 Correct 302 ms 224312 KB Output is correct
11 Correct 298 ms 224312 KB Output is correct
12 Correct 336 ms 224288 KB Output is correct
13 Correct 323 ms 224312 KB Output is correct
14 Correct 294 ms 224312 KB Output is correct
15 Correct 298 ms 226452 KB Output is correct
16 Correct 399 ms 243536 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 692 ms 324944 KB Output is correct
2 Correct 712 ms 324784 KB Output is correct
3 Correct 631 ms 323460 KB Output is correct
4 Correct 691 ms 324784 KB Output is correct
5 Correct 374 ms 224340 KB Output is correct
6 Correct 850 ms 258620 KB Output is correct
7 Correct 880 ms 258588 KB Output is correct
8 Correct 799 ms 244536 KB Output is correct
9 Correct 817 ms 265576 KB Output is correct
10 Correct 841 ms 265400 KB Output is correct
11 Correct 850 ms 265084 KB Output is correct
12 Correct 794 ms 265400 KB Output is correct
13 Correct 813 ms 265492 KB Output is correct
14 Correct 1006 ms 295744 KB Output is correct
15 Correct 1102 ms 309164 KB Output is correct
16 Correct 1136 ms 326320 KB Output is correct
17 Correct 870 ms 287032 KB Output is correct
18 Correct 872 ms 287304 KB Output is correct
19 Correct 869 ms 287508 KB Output is correct
20 Correct 643 ms 286876 KB Output is correct
21 Correct 480 ms 324360 KB Output is correct
22 Correct 475 ms 323984 KB Output is correct
23 Correct 669 ms 324780 KB Output is correct