oj.uz

Submission #641889

# Submission time Handle Problem Language Result Execution time Memory
641889 2022-09-17T18:37:04 Z Richem Railway Trip 2 (JOI22_ho_t4) C++14
52 / 100
 941 ms 111132 KB 
#include <iostream>
#include <stack>
using namespace std;

const int MAX_TRAJET = 2e5+42, MAX_POW = 19, MAX_FEUILLE = 262144, INF = 1e9;

int nbPos, distMax;
int nbTrajet;

int arbre[MAX_FEUILLE*2][2][MAX_POW];

int get(int deb, int fin, int id, int type) {
    deb += MAX_FEUILLE; fin += MAX_FEUILLE;

    int rep = INF;

    if(type == 1) rep = 0;

    while(deb <= fin) {
        if(deb % 2 == 1) {
            if(type == 0) rep = min(rep, arbre[deb++][0][id]);
            else rep = max(rep, arbre[deb++][1][id]);
        }
        if(fin % 2 == 0) {
            if(type == 0) rep = min(rep, arbre[fin--][0][id]);
            else rep = max(rep, arbre[fin--][1][id]);
        }

        deb /= 2;
        fin /= 2;
    }

    return rep;
}

void update(int pos, int val, int type, int id) {
    pos += MAX_FEUILLE;
    arbre[pos][type][id] = val;

    for(pos /= 2; pos > 0; pos /= 2) {
        int gauche = arbre[pos*2][type][id];
        int droite = arbre[pos*2+1][type][id];

        if(type == 0)
            arbre[pos][type][id] = min(gauche, droite);
        else
            arbre[pos][type][id] = max(gauche, droite);
    }
}

pair<int, int> posMax[MAX_TRAJET][MAX_POW];

void toutUpdate(int exp) {
    for(int pos = 0; pos < nbPos; pos++) {
        update(pos, posMax[pos][exp].first, 0, exp);
        update(pos, posMax[pos][exp].second, 1, exp);
    }
}

pair<int, int> calcInter(int exp, int deb, int fin) {
    int nouvDeb = get(deb, min(nbPos-1, fin + distMax - 1), exp, 0);
    int nouvFin = get(max(0, deb - distMax + 1), fin, exp, 1);

    return {nouvDeb, nouvFin};
}

void input() {
    for(int i = 0; i < MAX_FEUILLE*2; i++) {
        for(int j = 0; j < MAX_POW; j++) {
            arbre[i][0][j] = INF;
            arbre[i][1][j] = 0;
        }    
    }

    for(int i = 0; i < MAX_TRAJET; i++) 
        posMax[i][0].first = posMax[i][0].second = i;

    cin >> nbPos >> distMax >> nbTrajet;

    for(int i = 0; i < nbTrajet; i++) {
        int deb, fin;
        cin >> deb >> fin;
        deb--; fin--;

        if(deb <= fin) 
            posMax[deb][0].second = max(posMax[deb][0].second, fin);
        else
            posMax[deb][0].first = min(posMax[deb][0].first, fin);
    }        

    toutUpdate(0);

    for(int pos = 0; pos < nbPos; pos++) {
        posMax[pos][0].first = posMax[pos][0].second = pos;
        pair<int, int> ah = calcInter(0, pos, pos);

        posMax[pos][0].first = ah.first; posMax[pos][0].second = ah.second;
    }
}

void calcBl() {
    for(int exp = 1; exp < MAX_POW; exp++) {
        for(int pos = 0; pos < nbPos; pos++) {
            pair<int, int> ah = calcInter(exp-1, posMax[pos][exp-1].first, posMax[pos][exp-1].second);
            posMax[pos][exp].first = ah.first; posMax[pos][exp].second = ah.second;
        }

        toutUpdate(exp);
    }
}

int req(int depart, int arrive) {
    int deb = depart, fin = depart;
    int rep = 0;

    for(int exp = MAX_POW-1; exp >= 0; exp--) {
        pair<int, int> nouv = calcInter(exp, deb, fin);

        if(arrive > nouv.second || arrive < nouv.first) {
            rep += (1 << exp);
            deb = nouv.first; fin = nouv.second;
        }
    }

    if(rep+1 == (1 << MAX_POW))
        return -1;
    return rep+1;
}

int nbReq;

int main() {
    input();
    calcBl();

    cin >> nbReq;

    for(int i = 0; i < nbReq; i++) {
        int a,b;
        cin >> a >> b;

        cout << req(a-1, b-1) << endl;
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 107984 KB Output is correct
2 Correct 51 ms 107968 KB Output is correct
3 Correct 53 ms 108016 KB Output is correct
4 Correct 55 ms 108012 KB Output is correct
5 Correct 51 ms 107940 KB Output is correct
6 Correct 50 ms 107980 KB Output is correct
7 Correct 55 ms 107916 KB Output is correct
8 Correct 50 ms 108012 KB Output is correct
9 Correct 49 ms 107940 KB Output is correct
10 Correct 52 ms 108016 KB Output is correct
11 Correct 61 ms 108004 KB Output is correct
12 Correct 63 ms 107932 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 107984 KB Output is correct
2 Correct 51 ms 107968 KB Output is correct
3 Correct 53 ms 108016 KB Output is correct
4 Correct 55 ms 108012 KB Output is correct
5 Correct 51 ms 107940 KB Output is correct
6 Correct 50 ms 107980 KB Output is correct
7 Correct 55 ms 107916 KB Output is correct
8 Correct 50 ms 108012 KB Output is correct
9 Correct 49 ms 107940 KB Output is correct
10 Correct 52 ms 108016 KB Output is correct
11 Correct 61 ms 108004 KB Output is correct
12 Correct 63 ms 107932 KB Output is correct
13 Correct 61 ms 107980 KB Output is correct
14 Correct 63 ms 107976 KB Output is correct
15 Correct 62 ms 107980 KB Output is correct
16 Correct 69 ms 108044 KB Output is correct
17 Correct 73 ms 107980 KB Output is correct
18 Correct 71 ms 107968 KB Output is correct
19 Correct 67 ms 107940 KB Output is correct
20 Correct 67 ms 108040 KB Output is correct
21 Correct 70 ms 107932 KB Output is correct
22 Correct 69 ms 107972 KB Output is correct
23 Correct 67 ms 108104 KB Output is correct
24 Correct 73 ms 108052 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 667 ms 108948 KB Output is correct
2 Correct 671 ms 108920 KB Output is correct
3 Correct 731 ms 109120 KB Output is correct
4 Correct 644 ms 108864 KB Output is correct
5 Correct 574 ms 110320 KB Output is correct
6 Correct 613 ms 110320 KB Output is correct
7 Correct 551 ms 110156 KB Output is correct
8 Correct 506 ms 109160 KB Output is correct
9 Correct 482 ms 109176 KB Output is correct
10 Correct 580 ms 110316 KB Output is correct
11 Correct 592 ms 110316 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 775 ms 109656 KB Output is correct
2 Correct 718 ms 110944 KB Output is correct
3 Correct 941 ms 109824 KB Output is correct
4 Correct 688 ms 110552 KB Output is correct
5 Correct 714 ms 110812 KB Output is correct
6 Correct 696 ms 110884 KB Output is correct
7 Correct 796 ms 110980 KB Output is correct
8 Correct 782 ms 111132 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 922 ms 111124 KB Output is correct
2 Correct 822 ms 110132 KB Output is correct
3 Correct 771 ms 109428 KB Output is correct
4 Correct 818 ms 109200 KB Output is correct
5 Incorrect 771 ms 108784 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 107984 KB Output is correct
2 Correct 51 ms 107968 KB Output is correct
3 Correct 53 ms 108016 KB Output is correct
4 Correct 55 ms 108012 KB Output is correct
5 Correct 51 ms 107940 KB Output is correct
6 Correct 50 ms 107980 KB Output is correct
7 Correct 55 ms 107916 KB Output is correct
8 Correct 50 ms 108012 KB Output is correct
9 Correct 49 ms 107940 KB Output is correct
10 Correct 52 ms 108016 KB Output is correct
11 Correct 61 ms 108004 KB Output is correct
12 Correct 63 ms 107932 KB Output is correct
13 Correct 61 ms 107980 KB Output is correct
14 Correct 63 ms 107976 KB Output is correct
15 Correct 62 ms 107980 KB Output is correct
16 Correct 69 ms 108044 KB Output is correct
17 Correct 73 ms 107980 KB Output is correct
18 Correct 71 ms 107968 KB Output is correct
19 Correct 67 ms 107940 KB Output is correct
20 Correct 67 ms 108040 KB Output is correct
21 Correct 70 ms 107932 KB Output is correct
22 Correct 69 ms 107972 KB Output is correct
23 Correct 67 ms 108104 KB Output is correct
24 Correct 73 ms 108052 KB Output is correct
25 Correct 667 ms 108948 KB Output is correct
26 Correct 671 ms 108920 KB Output is correct
27 Correct 731 ms 109120 KB Output is correct
28 Correct 644 ms 108864 KB Output is correct
29 Correct 574 ms 110320 KB Output is correct
30 Correct 613 ms 110320 KB Output is correct
31 Correct 551 ms 110156 KB Output is correct
32 Correct 506 ms 109160 KB Output is correct
33 Correct 482 ms 109176 KB Output is correct
34 Correct 580 ms 110316 KB Output is correct
35 Correct 592 ms 110316 KB Output is correct
36 Correct 775 ms 109656 KB Output is correct
37 Correct 718 ms 110944 KB Output is correct
38 Correct 941 ms 109824 KB Output is correct
39 Correct 688 ms 110552 KB Output is correct
40 Correct 714 ms 110812 KB Output is correct
41 Correct 696 ms 110884 KB Output is correct
42 Correct 796 ms 110980 KB Output is correct
43 Correct 782 ms 111132 KB Output is correct
44 Correct 922 ms 111124 KB Output is correct
45 Correct 822 ms 110132 KB Output is correct
46 Correct 771 ms 109428 KB Output is correct
47 Correct 818 ms 109200 KB Output is correct
48 Incorrect 771 ms 108784 KB Output isn't correct
49 Halted 0 ms 0 KB -