oj.uz

Submission #979230

# Submission time Handle Problem Language Result Execution time Memory
979230 2024-05-10T12:01:11 Z sleepntsheep Rainforest Jumps (APIO21_jumps) C++17
23 / 100
 764 ms 38812 KB 
#pragma GCC optimize("O2,unroll-loops")
#include "jumps.h"

#include<assert.h>
#include <vector>
#include <algorithm>

int subtask = -1;

#define MAX_N 200000
#define MAX_M (2*MAX_N)

int N, head[MAX_N], nxt[MAX_M], vv[MAX_M], ng[MAX_N], pg[MAX_N], HI[MAX_N], H[MAX_N];
int dd[MAX_N], pp[MAX_N], jj[MAX_N], dd_[MAX_N], pp_[MAX_N], jj_[MAX_N];
int dd1[MAX_N],pp1[MAX_N],jj1[MAX_N],ee1[MAX_N];
int dd2[MAX_N],pp2[MAX_N],jj2[MAX_N],ee2[MAX_N];

/*
 * dd - high link
 * dd_ - low link
 * dd1 - left link
 * dd2 - right link */

void link(int u, int v)
{
    static int i = 1;
    nxt[i] = head[u];
    vv[i] = v;
    head[u] = i++;
}

void binlift_connect(int*dd,int*pp,int*jj,int p,int u)
{
    dd[u] = dd[p] + 1;
    pp[u] = p;
    jj[u] = dd[p] - dd[jj[p]] == dd[jj[p]] - dd[jj[jj[p]]] ? jj[jj[p]] : p;
}

void init(int N, std::vector<int> H) {
    for(auto&x:H)--x;
    ::N = N;
    if (N <= 200) subtask = 2;
    else if (N <= 2000) subtask = 3;
    int flag = 1;
    for (int i = 1; i < N; ++i) if (H[i] != H[i-1] + 1) flag = 0;
    if(flag) subtask = 1;

    static int stk[MAX_N], so;
    so = 0;

    for (int i = 0; i < N; stk[so++] = i++) while (so && H[stk[so-1]] < H[i]) ng[stk[so-1]]=i, link(stk[--so], i);
    while(so)ng[stk[--so]]=-1;
    for (int i = N - 1; i >= 0; stk[so++] = i--) while (so && H[stk[so-1]] < H[i]) pg[stk[so-1]]=i, link(stk[--so], i);
    while(so)pg[stk[--so]]=-1;

    for (int i = 0; i < N; ++i) HI[::H[i]=H[i]] = i;

    for (int j = N; j--;)
    {
        int i = HI[j];
        int high = (pg[i] == -1) ? ng[i] : (ng[i] == -1 ? pg[i] : (H[ng[i]] > H[pg[i]] ? ng[i] : pg[i]));
        int low = pg[i] + ng[i] - high;
        if (high != -1) binlift_connect(dd, pp, jj, high, i);
        else pp[i] = jj[i] = i;
        if (low != -1) binlift_connect(dd_, pp_, jj_, low, i);
        else pp_[i] = jj_[i] = i;
    }

    if (subtask == -1) subtask = 4;

    for(int i=0;i<N;++i)
    {
        /* left */
        if(pg[i]==-1) { pp1[i]=jj1[i]=i,dd1[i]=0; }
        else{
            binlift_connect(dd1,pp1,jj1,pg[i],i);
            if(jj1[i]==pp1[i])ee1[i]=H[pg[i]];
            else ee1[i]=std::max(ee1[jj1[pp1[i]]],ee1[pp1[i]]);
        }

        /* right */
        if(ng[i]==-1) { pp2[i]=jj2[i]=i,dd2[i]=0; }
        else {
            binlift_connect(dd2,pp2,jj2,ng[i],i);
            if(jj2[i]==pp2[i])ee2[i]=H[ng[i]];
            else ee2[i]=std::max(ee2[jj2[pp2[i]]],ee2[pp2[i]]);
        }
    }
    subtask=7;
}

int Q_COUNTER = 0;

int minimum_jumps(int A, int B, int C, int D) {
    ++Q_COUNTER;

    if (subtask == 1) return (A>D)?-1:(B>=C?0:C-B);

    if (subtask == 4 && Q_COUNTER > 5) subtask = 5;

    if(subtask <= 4)
    {
        static int d[MAX_N], qu[MAX_N], qh=0, qt=0,z=1e9;
        qh=qt=0,z=1e9;
        for(int j=0;j<N;++j)d[j]=1e9;
        for (int i = A; i <= B; ++i) d[qu[qh++]=i]=0;
        while(qh-qt) for(int u=qu[qt++],j=head[u];j;j=nxt[j]) if(d[vv[j]]>d[u]+1)d[vv[j]]=d[u]+1,qu[qh++]=vv[j];
        for (int j = C; j <= D; ++j)if(d[j]!=1e9&&d[j]<z)z=d[j];
        return(z<1e9?z:-1);
    }

    if (subtask == 5 && A != B) subtask = 6;
    if (subtask == 6 && C != D) subtask = 7;

    if (subtask == 6)
    {
        if(H[B]>H[C])return -1;
        int u=B;
        for(;pp1[u]!=u;)
        {
            if(jj1[u]>=A&&ee1[u]<H[C])u=jj1[u];
            else if(pp1[u]>=A&&H[pp1[u]]<H[C])u=pp1[u];
            else break;
        }
        A=u;
    }

    if (subtask == 5 || subtask == 6)
    {
        if(A==-1)return -1;
        int u=A,u1;
        for(;pp[u]!=u;)
        {
            if (H[jj[u]]<=H[C])u=jj[u];
            else if(H[pp[u]]<=H[C])u=pp[u];
            else break;
        }
        u1=u;
        for(;pp_[u]!=u;)
        {
            if(H[jj_[u]]<=H[C])u=jj_[u];
            else if(H[pp_[u]]<=H[C])u=pp_[u];
            else break;
        }
        if(u!=C)return -1;
        return dd_[u1]-dd_[u]+dd[A]-dd[u1];
    }

    if (subtask == 7)
    {
        int highest_left;
        {
            int u=B;
            for(;pp1[u] != u;)
            {
                if(jj1[u]>=A)u=jj1[u];
                else if(pp1[u]>=A)u=pp1[u];
                else break;
            }
            highest_left=u;
        }
        assert(highest_left == B);


        /* the right endpoint is a position that is at lower_bound(highest_left) */
        {
            int u=C;
            for(;pp2[u]!=u;)
            {
                if(jj2[u]<=D&&ee2[u]<H[highest_left])u=jj2[u];
                else if(pp2[u]<=D&&H[pp2[u]]<H[highest_left])u=pp2[u];
                else break;
            }
            if (u!=pp2[u]&&pp2[u]<=D)u=pp2[u];
            assert(C == u);
            C=u;
        }

        /* select highest left endpoint possible */
        {
            int u=B;
            for(;pp1[u]!=u;)
            {
                if(jj1[u]>=A&&ee1[u]<H[C])u=jj1[u];
                else if(pp1[u]>=A&&H[pp1[u]]<H[C])u=pp1[u];
                else break;
            }
            //assert(B==u);
            A=u;
        }

        {
            int u=A,u1;
            for(;pp[u]!=u;)
            {
                if (H[jj[u]]<=H[C])u=jj[u];
                else if(H[pp[u]]<=H[C])u=pp[u];
                else break;
            }
            u1=u;
            for(;pp_[u]!=u;)
            {
                if(H[jj_[u]]<=H[C])u=jj_[u];
                else if(H[pp_[u]]<=H[C])u=pp_[u];
                else break;
            }
            if(u!=C)return -1;
            return dd_[u1]-dd_[u]+dd[A]-dd[u1];
        }
    }

    return -1;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 2 ms 14680 KB Output is correct
3 Runtime error 37 ms 38812 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 17240 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 17240 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 17240 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8692 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 1 ms 8536 KB Output is correct
4 Correct 189 ms 13596 KB Output is correct
5 Correct 690 ms 21432 KB Output is correct
6 Correct 453 ms 12604 KB Output is correct
7 Correct 667 ms 21216 KB Output is correct
8 Correct 414 ms 14536 KB Output is correct
9 Correct 733 ms 21388 KB Output is correct
10 Correct 590 ms 21184 KB Output is correct
11 Correct 605 ms 21956 KB Output is correct
12 Correct 751 ms 19648 KB Output is correct
13 Correct 613 ms 21456 KB Output is correct
14 Correct 677 ms 21676 KB Output is correct
15 Correct 607 ms 21476 KB Output is correct
16 Correct 747 ms 21692 KB Output is correct
17 Correct 2 ms 14680 KB Output is correct
18 Correct 2 ms 14680 KB Output is correct
19 Correct 3 ms 14680 KB Output is correct
20 Correct 4 ms 15044 KB Output is correct
21 Correct 3 ms 14680 KB Output is correct
22 Correct 3 ms 14772 KB Output is correct
23 Correct 3 ms 14680 KB Output is correct
24 Correct 3 ms 16728 KB Output is correct
25 Correct 2 ms 14680 KB Output is correct
26 Correct 2 ms 14836 KB Output is correct
27 Correct 10 ms 14680 KB Output is correct
28 Correct 14 ms 14680 KB Output is correct
29 Correct 13 ms 14680 KB Output is correct
30 Correct 15 ms 14680 KB Output is correct
31 Correct 14 ms 9044 KB Output is correct
32 Correct 1 ms 6488 KB Output is correct
33 Correct 23 ms 15992 KB Output is correct
34 Correct 33 ms 21328 KB Output is correct
35 Correct 32 ms 19880 KB Output is correct
36 Correct 36 ms 21240 KB Output is correct
37 Correct 27 ms 21744 KB Output is correct
38 Correct 24 ms 21624 KB Output is correct

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8692 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 1 ms 8536 KB Output is correct
4 Correct 189 ms 13596 KB Output is correct
5 Correct 690 ms 21432 KB Output is correct
6 Correct 453 ms 12604 KB Output is correct
7 Correct 667 ms 21216 KB Output is correct
8 Correct 414 ms 14536 KB Output is correct
9 Correct 733 ms 21388 KB Output is correct
10 Correct 590 ms 21184 KB Output is correct
11 Correct 605 ms 21956 KB Output is correct
12 Correct 751 ms 19648 KB Output is correct
13 Correct 613 ms 21456 KB Output is correct
14 Correct 677 ms 21676 KB Output is correct
15 Correct 607 ms 21476 KB Output is correct
16 Correct 747 ms 21692 KB Output is correct
17 Correct 2 ms 14680 KB Output is correct
18 Correct 2 ms 14680 KB Output is correct
19 Correct 3 ms 14680 KB Output is correct
20 Correct 4 ms 15044 KB Output is correct
21 Correct 3 ms 14680 KB Output is correct
22 Correct 3 ms 14772 KB Output is correct
23 Correct 3 ms 14680 KB Output is correct
24 Correct 3 ms 16728 KB Output is correct
25 Correct 2 ms 14680 KB Output is correct
26 Correct 2 ms 14836 KB Output is correct
27 Correct 10 ms 14680 KB Output is correct
28 Correct 14 ms 14680 KB Output is correct
29 Correct 13 ms 14680 KB Output is correct
30 Correct 15 ms 14680 KB Output is correct
31 Correct 14 ms 9044 KB Output is correct
32 Correct 1 ms 6488 KB Output is correct
33 Correct 23 ms 15992 KB Output is correct
34 Correct 33 ms 21328 KB Output is correct
35 Correct 32 ms 19880 KB Output is correct
36 Correct 36 ms 21240 KB Output is correct
37 Correct 27 ms 21744 KB Output is correct
38 Correct 24 ms 21624 KB Output is correct
39 Correct 2 ms 14680 KB Output is correct
40 Correct 2 ms 16728 KB Output is correct
41 Correct 2 ms 16728 KB Output is correct
42 Correct 174 ms 17688 KB Output is correct
43 Correct 759 ms 21420 KB Output is correct
44 Correct 535 ms 15968 KB Output is correct
45 Correct 764 ms 21424 KB Output is correct
46 Correct 462 ms 17084 KB Output is correct
47 Correct 746 ms 21220 KB Output is correct
48 Correct 683 ms 21188 KB Output is correct
49 Correct 760 ms 21696 KB Output is correct
50 Correct 654 ms 21188 KB Output is correct
51 Correct 578 ms 21208 KB Output is correct
52 Correct 599 ms 21844 KB Output is correct
53 Correct 597 ms 21464 KB Output is correct
54 Correct 664 ms 19280 KB Output is correct
55 Correct 1 ms 2392 KB Output is correct
56 Runtime error 108 ms 38560 KB Execution killed with signal 6
57 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 2 ms 14680 KB Output is correct
3 Runtime error 37 ms 38812 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -