Submission #200786

#	Time	Username	Problem	Language	Result	Execution time	Memory
200786		ho94949	Railway Trip (JOI17_railway_trip)	C++17	45 / 100	2051 ms	14036 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 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 (stderr)

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