Submission #302922

#	Time	Username	Problem	Language	Result	Execution time	Memory
302922		balbit	Railway Trip (JOI17_railway_trip)	C++14	0 / 100	192 ms	25344 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 BALBIT
#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];

signed main(){
    IOS();

    cin>>n>>k>>q;
    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) {
            bst[j][i][0] = bst[j-1][bst[j-1][i][0]][0];
            bst[j][i][1] = bst[j-1][bst[j-1][i][1]][1];

            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];
            }
        }
    }
    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;
        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;
                for (int j = 20; j>=0; --j) {
                    if (a[bst[j][X][dir^df]] < mx + df) {
                        steps += (1<<j);
                        bug(j, bst[j][X][dir], bst[j][X][dir^1]);
                        X = bst[j][X][dir^df];
                    }
                }
                bug(steps, X, y);
                bug(a[X], mx + df, mx, df);
                if (a[X] >= mx+df) --steps;
                else {
                    if (a[bst[0][X][dir^df]] > mx && df == 0) {
                        int tmp=X;
                        X = to[X][dir^1] ^ to[X][dir] ^ bst[0][X][dir^df];
                        if (a[X] != mx) X=bst[0][tmp][dir^df]; bug("HI");
                    }
                    else X = bst[0][X][dir^df];
                }
            }
            int smol = min(a[T[0]], a[T[1]]);
            bug(steps, smol);
            MN(ans[id] , (a[T[0]] != a[T[1]]) + steps + leq(upd[smol], T[1]) - leq(upd[smol], T[0]-1));
//            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;
    }
}

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