oj.uz

Submission #304317

# Submission time Handle Problem Language Result Execution time Memory
304317 2020-09-21T06:07:13 Z balbit Railway Trip (JOI17_railway_trip) C++14
100 / 100
 740 ms 28136 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 1 ms 512 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 768 KB Output is correct
2 Correct 43 ms 19448 KB Output is correct
3 Correct 45 ms 19576 KB Output is correct
4 Correct 44 ms 19300 KB Output is correct
5 Correct 43 ms 19320 KB Output is correct
6 Correct 47 ms 19356 KB Output is correct
7 Correct 54 ms 23032 KB Output is correct
8 Correct 41 ms 22260 KB Output is correct
9 Correct 48 ms 22264 KB Output is correct
10 Correct 45 ms 20336 KB Output is correct
11 Correct 53 ms 22520 KB Output is correct
12 Correct 50 ms 20728 KB Output is correct
13 Correct 50 ms 20216 KB Output is correct
14 Correct 51 ms 22352 KB Output is correct
15 Correct 50 ms 20728 KB Output is correct
16 Correct 48 ms 20256 KB Output is correct
17 Correct 46 ms 21624 KB Output is correct
18 Correct 48 ms 21708 KB Output is correct
19 Correct 50 ms 23928 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 407 ms 21768 KB Output is correct
2 Correct 408 ms 21928 KB Output is correct
3 Correct 396 ms 21900 KB Output is correct
4 Correct 395 ms 21896 KB Output is correct
5 Correct 404 ms 21768 KB Output is correct
6 Correct 410 ms 21896 KB Output is correct
7 Correct 408 ms 21896 KB Output is correct
8 Correct 405 ms 22248 KB Output is correct
9 Correct 706 ms 22276 KB Output is correct
10 Correct 705 ms 23660 KB Output is correct
11 Correct 701 ms 23660 KB Output is correct
12 Correct 704 ms 23652 KB Output is correct
13 Correct 715 ms 23660 KB Output is correct
14 Correct 416 ms 23396 KB Output is correct
15 Correct 368 ms 23324 KB Output is correct
16 Correct 369 ms 23024 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 390 ms 25392 KB Output is correct
2 Correct 399 ms 25320 KB Output is correct
3 Correct 359 ms 22120 KB Output is correct
4 Correct 376 ms 22760 KB Output is correct
5 Correct 740 ms 24556 KB Output is correct
6 Correct 507 ms 26612 KB Output is correct
7 Correct 553 ms 25444 KB Output is correct
8 Correct 547 ms 24428 KB Output is correct
9 Correct 522 ms 26600 KB Output is correct
10 Correct 515 ms 25448 KB Output is correct
11 Correct 520 ms 24552 KB Output is correct
12 Correct 549 ms 26728 KB Output is correct
13 Correct 529 ms 25576 KB Output is correct
14 Correct 490 ms 27368 KB Output is correct
15 Correct 481 ms 27496 KB Output is correct
16 Correct 491 ms 28136 KB Output is correct
17 Correct 397 ms 26724 KB Output is correct
18 Correct 402 ms 26856 KB Output is correct
19 Correct 408 ms 26900 KB Output is correct
20 Correct 342 ms 26480 KB Output is correct
21 Correct 408 ms 25836 KB Output is correct
22 Correct 407 ms 25828 KB Output is correct
23 Correct 407 ms 27884 KB Output is correct