oj.uz

Submission #200799

# Submission time Handle Problem Language Result Execution time Memory
200799 2020-02-08T07:30:47 Z ho94949 Railway Trip (JOI17_railway_trip) C++17
100 / 100
 411 ms 122328 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 sparse[20][6*MAXN];
int pdist[20][6*MAXN];
void build_sparse_raw(vector<int> P, vector<int> D)
{
    int N = P.size();
    for(int i=0; i<N; ++i)
        sparse[0][i] = P[i], pdist[0][i] = D[i];
    for(int j=1; j<20; ++j)
    {
        for(int i=0; i<N; ++i)
        {
            sparse[j][i] = sparse[j-1][sparse[j-1][i]];
            pdist[j][i] = pdist[j-1][i] + pdist[j-1][sparse[j-1][i]];
        }
    }
}
int encode(int a, int b)
{
    return 3*a+b+1;
}
pair<int, int> decode(int a)
{
    return make_pair((a-1)/3, (a-1)%3);
}
void build_sparse()
{
    vector<int> P(3*tp+1), D(3*tp+1);
    for(int i=0; i<tp; ++i)
    {
        for(int j=0; j<3; ++j)
        {
            int from = encode(i, j);
            P[from] = encode(n[i].p, n[i].pt[j]);
            D[from] = n[i].pd[j];
        }
    }
    P[0] = P[1] = P[2] = P[3] = D[0] = D[1] = D[2] = D[3] = 0;
    build_sparse_raw(P, D);
}

int dist(int a, int b)
{
    if(a>b) swap(a, b);

    int av = encode(last_left[a], LEFT);
    int bv = encode(last_right[b], RIGHT);
    int dv = 0;
    auto eqp = [&](){return av==bv||n[decode(av).first].p == n[decode(bv).first].p;};
    auto ha = [&](){return n[decode(av).first].h;};
    auto hb = [&](){return n[decode(bv).first].h;};
    bool swapped = false;
    if(hb()>ha())
    {
        swap(av, bv);
        swapped = true;
    }
    int hdiff = ha()-hb();
    for(int i=19; i>=0; --i)
    {
        if(hdiff&(1<<i))
        {
            dv += pdist[i][av];
            av = sparse[i][av];
        }
    }
    for(int i=19; i>=0; --i)
    {
        int pav = av, pbv = bv;
        av = sparse[i][av], bv = sparse[i][bv];
        if(eqp())
        {
            av=pav; bv=pbv;
        }
        else
        {
            dv += pdist[i][pav];
            dv += pdist[i][pbv];
        }
    }
    if(!eqp())
    {
        dv += pdist[0][av];
        dv += pdist[0][bv];
        av = sparse[0][av];
        bv = sparse[0][bv];
    }
    if(swapped) swap(av, bv);
    int a1, a2, b1, b2;
    tie(a1, a2) = decode(av);
    tie(b1, b2) = decode(bv);
    return calc_dist(a1, a2, b1, b2)+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();
    build_sparse();
    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:216: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:218: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:225: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 888 KB Output is correct
2 Correct 5 ms 884 KB Output is correct
3 Correct 5 ms 888 KB Output is correct
4 Correct 5 ms 888 KB Output is correct
5 Correct 5 ms 888 KB Output is correct
6 Correct 5 ms 888 KB Output is correct
7 Correct 6 ms 888 KB Output is correct
8 Correct 5 ms 888 KB Output is correct
9 Correct 5 ms 632 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1912 KB Output is correct
2 Correct 132 ms 98400 KB Output is correct
3 Correct 130 ms 104960 KB Output is correct
4 Correct 137 ms 109788 KB Output is correct
5 Correct 150 ms 111892 KB Output is correct
6 Correct 154 ms 114552 KB Output is correct
7 Correct 156 ms 115100 KB Output is correct
8 Correct 102 ms 58968 KB Output is correct
9 Correct 117 ms 82028 KB Output is correct
10 Correct 113 ms 72908 KB Output is correct
11 Correct 119 ms 83832 KB Output is correct
12 Correct 122 ms 83960 KB Output is correct
13 Correct 126 ms 83704 KB Output is correct
14 Correct 132 ms 83832 KB Output is correct
15 Correct 123 ms 83960 KB Output is correct
16 Correct 126 ms 83960 KB Output is correct
17 Correct 159 ms 115040 KB Output is correct
18 Correct 183 ms 115064 KB Output is correct
19 Correct 142 ms 115168 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 101976 KB Output is correct
2 Correct 329 ms 98808 KB Output is correct
3 Correct 322 ms 102520 KB Output is correct
4 Correct 330 ms 103160 KB Output is correct
5 Correct 338 ms 103760 KB Output is correct
6 Correct 359 ms 104984 KB Output is correct
7 Correct 347 ms 105080 KB Output is correct
8 Correct 277 ms 73248 KB Output is correct
9 Correct 255 ms 59096 KB Output is correct
10 Correct 252 ms 59096 KB Output is correct
11 Correct 265 ms 59268 KB Output is correct
12 Correct 251 ms 59100 KB Output is correct
13 Correct 253 ms 59228 KB Output is correct
14 Correct 257 ms 59260 KB Output is correct
15 Correct 252 ms 60408 KB Output is correct
16 Correct 291 ms 70116 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 115320 KB Output is correct
2 Correct 362 ms 115296 KB Output is correct
3 Correct 339 ms 115064 KB Output is correct
4 Correct 361 ms 115320 KB Output is correct
5 Correct 256 ms 59096 KB Output is correct
6 Correct 355 ms 82168 KB Output is correct
7 Correct 355 ms 82176 KB Output is correct
8 Correct 327 ms 73164 KB Output is correct
9 Correct 360 ms 84088 KB Output is correct
10 Correct 376 ms 84216 KB Output is correct
11 Correct 368 ms 83960 KB Output is correct
12 Correct 356 ms 83960 KB Output is correct
13 Correct 369 ms 84216 KB Output is correct
14 Correct 376 ms 103928 KB Output is correct
15 Correct 399 ms 111992 KB Output is correct
16 Correct 411 ms 122328 KB Output is correct
17 Correct 401 ms 96504 KB Output is correct
18 Correct 390 ms 97016 KB Output is correct
19 Correct 394 ms 97144 KB Output is correct
20 Correct 378 ms 93944 KB Output is correct
21 Correct 334 ms 115320 KB Output is correct
22 Correct 333 ms 115440 KB Output is correct
23 Correct 371 ms 115452 KB Output is correct