Submission #304317

#	Time	Username	Problem	Language	Result	Execution time	Memory
304317		balbit	Railway Trip (JOI17_railway_trip)	C++14	100 / 100	740 ms	28136 KiB

railway_trip

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBITe
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif

const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;


void GG(){cout<<"0\n"; exit(0);}

ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mo;
        a = a*a %mo;
        n>>=1;
    }
    return re;
}

ll inv (ll b, ll mo = mod){
    if (b==1) return b;
    return (mo-mo/b) * inv(mo%b,mo) % mo;
}

const int maxn = 1e5+5;

int n,k,q;
int bst[21][maxn][2];
int a[maxn];

int s[maxn];

ll QU(int e) {
    ll re = 0;
    for (++e; e>0; e-=e&-e) re += s[e];
    return re;
}

void MO(int e, int v) {
    for (++e; e<maxn; e+=e&-e) s[e] += v;
}

int seg[2 * maxn];

void build() {  // build the tree
  for (int i = maxn - 1; i > 0; --i) seg[i] = max(seg[i<<1] , seg[i<<1|1]);
}

void modify(int p, int value) {  // set value at position p
    for (seg[p += maxn] = value; p > 1; p >>= 1) seg[p>>1] = max(seg[p] , seg[p^1]);
}

int query(int l, int r) {  // sum on interval [l, r)
    int res = 0;
    for (l += maxn, r += maxn; l < r; l >>= 1, r >>= 1) {
        if (l&1) res = max(res, seg[l++]);
        if (r&1) res = max(res, seg[--r]);
    }
    return res;
}

struct qq{
    int x,y,mx,id;
};

int leq(vector<int> & x, int a) {
    return upper_bound(ALL(x), a) - x.begin();
}

int to[maxn][2];

void walk(array<int, 2> &A) {
    A[0] = bst[0][A[0]][0];
    A[1] = bst[0][A[1]][1];
    if (a[A[0]] != a[A[1]]) {
        if (a[A[0]] > a[A[1]]) A[1] = A[0];
        else A[0] = A[1];
    }
}

void ass(bool x) {if (!x) while(1); }

signed main(){
    IOS();
//    cout<<"1\n3\n0\n"; return 0;
    cin>>n>>k>>q;
//    assert(n<=25);
    for (int i = 0; i<n; ++i) {
        cin>>a[i];
        modify(i,a[i]);
    }
//    build();
    bug(query(0,3));
    vector<int> ps = {0};
    for (int i = 0; i<n; ++i) {
        while (a[ps.back()] < a[i]) {
            ps.pop_back();
        }
        bst[0][i][0] = ps.back();
        ps.pb(i);
    }
    ps = {n-1};
    for (int i = n-1; i>=0; --i) {
        while (a[ps.back()] < a[i]) {
            ps.pop_back();
        }
        bst[0][i][1] = ps.back();
        ps.pb(i);
    }
    for (int i = 0; i<n; ++i) {
        to[i][0] = bst[0][i][0];
        to[i][1] = bst[0][i][1];
//        tie(to[i][0], to[i][1]) = make_pair(bst[0][i][0], bst[0][i][1]);
        if (a[bst[0][i][0]] != a[bst[0][i][1]]) {
            if (a[bst[0][i][0]] < a[bst[0][i][1]]) {
                bst[0][i][0] = bst[0][i][1];
            }else{
                bst[0][i][1] = bst[0][i][0];
            }
        }
        bug(bst[0][i][0], bst[0][i][1]);
    }
    for (int j = 1; j<21; ++j) {
        for (int i = 0; i<n; ++i) {
//            vector<int> tv = {}
            int bt = -1;
            int L = 0, R = 0;
            for (int a1 = 0; a1<2; ++a1) for (int a2 = 0; a2<2; ++a2) {
                int it = bst[j-1][bst[j-1][i][a1]][a2];
                if (a[it] > bt) {
                    L = R = it; bt = a[it];
                }
                if (a[it] == bt) {
                    L = min(L, it); R = max(R, it);
                }
//                MX(bst, )
            }
            bst[j][i][0] = L;
            bst[j][i][1] = R;


            if (a[bst[j][i][0]] != a[bst[j][i][1]]) if (a[bst[j][i][0]] < a[bst[j][i][1]]) {
                bst[j][i][0] = bst[j][i][1];
            }else{
                bst[j][i][1] = bst[j][i][0];
            }
            if (j == 2) {
                array<int,2> tmp = {{bst[j][i][0], bst[j][i][1]}};
                array<int,2> t2 = {{i,i}}; walk(t2); walk(t2); walk(t2); walk(t2);
                assert(tmp == t2);
            }
        }
    }
    vector<qq > ques;

    for (int cnt = 0; cnt < q; ++cnt) {
        int x,y; cin>>x>>y; --x; --y;
        if (x > y) swap(x,y);
        ques.pb({x,y,query(x,y + 1), cnt});
    }
//    sort(ALL(ques), [&](qq  A, qq  b){return A.mx > b.mx;});
    vector<vector<int> > upd (k+1);
    for (int i = 0; i<n; ++i) {
        upd[a[i]].pb(i);
    }
    int tmp = k+1;
    vector<int> ans(q,100000000);
    vector<qq> resv;
    for (int cnt = 0; cnt<q; ++cnt) {
        int x = ques[cnt].x, y = ques[cnt].y;
        assert(x!=y);
        int mx = ques[cnt].mx;
        int id = ques[cnt].id;
//        if (id != 3) continue;
        // x is lower
        bug(x+1,y+1,mx,id);
        for (int df = 0; df < 2; ++df) {
            if (df>0 && mx == k) break;
            array<int, 2> T = {{x,y}};

            int steps = 0;
            for (int &X : T) {
                int dir = X<y;
                array<int, 2> at = {{X,X}};
                for (int j = 20; j>=0; --j) {
                    array<int, 2> at2;
                    int bt = -1;
                    int L = 0, R = 0;
                    for (int a1 = 0; a1<2; ++a1) for (int a2 = 0; a2<2; ++a2) {
                        int it = bst[j][at[a1]][a2];
                        if (a[it] > bt) {
                            L = R = it; bt = a[it];
                        }
                        if (a[it] == bt) {
                            L = min(L, it); R = max(R, it);
                        }
        //                MX(bst, )
                    }
                    at2[0] = L;
                    at2[1] = R;

                    if (a[at2[0]] < mx + df) {
                        steps += (1<<j);
//                        bug(j, bst[j][X][dir], bst[j][X][dir^1]);
////                        X = bst[j][X][dir];
                        at = at2;
                    }
                }
                while (1) {
                    array<int, 2> at2 = at; walk(at2);
                    if (a[at2[0]] < mx+df) {
                        assert(0);
                        steps++; at=at2;
                    }else break;
                }
                X=at[dir];
                bug(steps, X, y);
                bug(a[X], mx + df, mx, df);
                if (a[X] >= mx+df) --steps;
                else {
                    if (df == 0) {
                        if (a[to[X][dir]] >= mx) X = to[X][dir];
                        else X = bst[0][X][dir];
                        if (a[X] < mx) {
                            X = at[dir^1];
                            if (a[to[X][dir]] >= mx) X = to[X][dir^1];
                            else {
                                X = bst[0][X][dir];
                                if (a[X] < mx) X=bst[0][X][dir^1];
                                ass(a[X] >= mx);
                            }
                        }
                    }else{
                        walk(at);
                        if (a[at[dir]] >= mx+df) {
                            X = at[dir];
                        }else{
                            X = at[dir^1];
                            assert(a[X] >= mx + df);
                        }
                    }
                }
            }

//            assert(T[0]<=T[1]);
            int smol = min(a[T[0]], a[T[1]]);
            if (df == 0)
                assert(smol >= mx + df);
//            if (smol < mx + df) continue;
            bug(smol, mx);
            bug(steps, smol);
            MN(ans[id] , (a[T[0]] != a[T[1]]) + steps + (T[0] <= T[1]?leq(upd[smol], T[1]) - leq(upd[smol], T[0]-1) : 0));
//            resv.pb(T[0], T[1], , cnt) ;
        }
//        bug(nxt, y);

    }
//    for (int cnt = 0; cnt < q; ++cnt) {
//        while (tmp > a[y]) {
//            --tmp;
//            bug(tmp, y, a[y]);
//            for (int w : upd[tmp]) {
//                MO(w,1);
//            }
//        }
//    }
    for (int i = 0; i<q; ++i) {
        cout<<ans[i]<<endl;
    }
}
/*
9 3 1
3 1 1 2 2 1 1 1 3
2 6
*/

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 25 / 25
• Subtask 4: 55 / 55