Submission #200799

#	Time	Username	Problem	Language	Result	Execution time	Memory
200799		ho94949	Railway Trip (JOI17_railway_trip)	C++17	100 / 100	411 ms	122328 KiB

railway_trip

#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 (stderr)

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 / 5
• Subtask 2: 15 / 15
• Subtask 3: 25 / 25
• Subtask 4: 55 / 55