oj.uz

답안 #1065143

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1065143 2024-08-19T00:39:07 Z oscar1f Railway Trip (JOI17_railway_trip) C++17
0 / 100
 2000 ms 16608 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);
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);
    }
}

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++;
        }
        hautMax--;
        rep=distDro[hautMax][0]+distGau[hautMax][1]+numEgau[voisGau[hautMax][1]]-numEgau[voisDro[hautMax][0]];
        cout<<rep-1<<"\n";
    }
    return 0;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Incorrect 1 ms 8540 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 8796 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 15976 KB Output is correct
2 Incorrect 78 ms 15956 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2044 ms 16608 KB Time limit exceeded
2 Halted 0 ms 0 KB -