oj.uz

Submission #200786

# Submission time Handle Problem Language Result Execution time Memory
200786 2020-02-08T07:02:04 Z ho94949 Railway Trip (JOI17_railway_trip) C++17
45 / 100
 2000 ms 14036 KB 
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 131072;
int N, K, Q;
int L[MAXN];

enum {LEFT=0, MID=1, RIGHT=2};
struct Node
{
    int l, r, p;
    int pos; //position
    int h; //height
    int pt[3], pd[3]; //parent type, parent distance
} n[2*MAXN];
int tp = 0;



int last_left[MAXN], last_right[MAXN];
int idx[2*MAXN];
void setv(int a, int v)
{
    L[a] = v;
    idx[a+MAXN] = a;
    a += MAXN;
    while((a=a/2))
    {
        if(L[idx[2*a+1]] > L[idx[2*a]] ) idx[a] = idx[2*a+1];
        else idx[a] = idx[2*a];
    }
}
int getv(int a, int b)
{
    int ans = a;
    a += MAXN; b += MAXN;
    while(a<=b)
    {
        if(a%2==1)
        {
            if(L[idx[a]]>L[ans]) ans = idx[a];
            ++a;
        }
        if(b%2==0)
        {
            if(L[idx[b]]>L[ans]) ans = idx[b];
            --b;
        }
        a /=2; b/=2;
    }
    return ans;
}
vector<int> get_maxes(int from, int to)
{
    vector<int> ans;
    int q = getv(from, to); int qv = L[q];
    ans.push_back(q);
    setv(q, 0);
    assert(qv != 0);
    while( L[(q=getv(from, to))] == qv)
    {
        ans.push_back(q);
        setv(q, 0);
    }
    sort(ans.begin(), ans.end());
    for(auto x: ans) setv(x, qv);
    return ans;
}
void build_rec(int id)
{
    int from = n[id].l, to = n[id].r, p = id, h = n[id].h;
    if(from != -1) last_left[from] = id;
    if(to != N) last_right[to] = id;
    if(to-from==1) return;
    vector<int> child_ind = get_maxes(from+1, to-1);
    for(int i=0; i<(int)child_ind.size()+1; ++i)
    {
        n[tp].l = (i==0)?from:child_ind[i-1];
        n[tp].r = (i==(int)child_ind.size())?to:child_ind[i];
        n[tp].p = p; n[tp].h = h+1; n[tp].pos = i;
        for(int t=0; t<3; ++t)
        {
            int ldist = i; if(t==RIGHT) ++ldist;
            int rdist = (int)child_ind.size()-i; if(t==LEFT) ++rdist;
            if(ldist < rdist)
                n[tp].pt[t] = LEFT, n[tp].pd[t] = ldist;
            else if(ldist == rdist)
                n[tp].pt[t] = MID, n[tp].pd[t] = ldist;
            else
                n[tp].pt[t] = RIGHT, n[tp].pd[t] = rdist;
        }
        build_rec(tp++);
    }
}

int calc_dist(int aind, int atype, int bind, int btype)
{
    if(aind == bind)
    {
        if(atype==LEFT&&btype==RIGHT) return 1;
        else return 0;
    }
    int ans1 = n[bind].pos-n[aind].pos-1;
    if(atype==LEFT) ++ans1;
    if(btype==RIGHT) ++ans1;
    
    if(n[aind].p == 0) return ans1;

    return min(ans1,
        n[aind].pd[atype] + n[bind].pd[btype] + 
        (n[aind].pt[atype] == LEFT && n[bind].pt[btype] == RIGHT)
    );

}
int dist(int a, int b)
{
    if(a>b) swap(a, b);
    int aind = last_left[a], atype = LEFT;
    int bind = last_right[b], btype = RIGHT;
    int dv = 0;
    while(n[aind].p != n[bind].p) //until they are sibling rel
    {
        if(n[aind].h < n[bind].h)
        {
            //take b parent
            int nbind = n[bind].p;
            int nbtype = n[bind].pt[btype];
            dv += n[bind].pd[btype];
            bind = nbind; btype = nbtype;
        }
        else
        {
            //take a parent
            int naind = n[aind].p;
            int natype = n[aind].pt[atype];
            dv += n[aind].pd[atype];
            aind = naind; atype = natype;
        }
    }
    return calc_dist(aind, atype, bind, btype)+dv;
}

void build()
{
    n[tp].l = -1; n[tp].r = N; n[tp].p = -1; n[tp].h = 0;
    build_rec(tp++);
    
}
int main()
{
    scanf("%d%d%d", &N, &K, &Q);
    for(int i=0; i<N; ++i)
        scanf("%d", L+i);
    for(int i=0; i<N; ++i) setv(i, L[i]);
    build();
    while(Q--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", dist(a-1, b-1)-1);
    }
}

Compilation message

railway_trip.cpp: In function 'int main()':
railway_trip.cpp:150:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &N, &K, &Q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
railway_trip.cpp:152:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", L+i);
         ~~~~~^~~~~~~~~~~
railway_trip.cpp:158:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 6 ms 376 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 55 ms 9980 KB Output is correct
3 Correct 61 ms 10488 KB Output is correct
4 Correct 64 ms 10872 KB Output is correct
5 Correct 59 ms 11000 KB Output is correct
6 Correct 63 ms 11256 KB Output is correct
7 Correct 75 ms 11512 KB Output is correct
8 Correct 61 ms 7408 KB Output is correct
9 Correct 73 ms 12792 KB Output is correct
10 Correct 64 ms 10572 KB Output is correct
11 Correct 71 ms 10976 KB Output is correct
12 Correct 68 ms 11128 KB Output is correct
13 Correct 68 ms 11000 KB Output is correct
14 Correct 72 ms 11000 KB Output is correct
15 Correct 72 ms 11060 KB Output is correct
16 Correct 69 ms 11000 KB Output is correct
17 Correct 69 ms 11512 KB Output is correct
18 Correct 65 ms 11512 KB Output is correct
19 Correct 66 ms 11768 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 11768 KB Output is correct
2 Correct 139 ms 11724 KB Output is correct
3 Correct 132 ms 12024 KB Output is correct
4 Correct 131 ms 11896 KB Output is correct
5 Correct 144 ms 12024 KB Output is correct
6 Correct 140 ms 12024 KB Output is correct
7 Correct 137 ms 12024 KB Output is correct
8 Correct 107 ms 9764 KB Output is correct
9 Correct 117 ms 8664 KB Output is correct
10 Correct 105 ms 8664 KB Output is correct
11 Correct 110 ms 8668 KB Output is correct
12 Correct 105 ms 8668 KB Output is correct
13 Correct 109 ms 8664 KB Output is correct
14 Correct 120 ms 8568 KB Output is correct
15 Correct 117 ms 8568 KB Output is correct
16 Correct 155 ms 9284 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 12536 KB Output is correct
2 Correct 181 ms 12580 KB Output is correct
3 Correct 181 ms 12704 KB Output is correct
4 Correct 190 ms 12536 KB Output is correct
5 Correct 110 ms 8536 KB Output is correct
6 Execution timed out 2051 ms 14036 KB Time limit exceeded
7 Halted 0 ms 0 KB -