oj.uz

답안 #304125

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
304125 2020-09-21T03:10:02 Z balbit Railway Trip (JOI17_railway_trip) C++14
20 / 100
 225 ms 43016 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) {
            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;
        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 = {{bst[j][at[0]][0],bst[j][at[1]][1]}};
                    if (a[at2[0]] != a[at2[1]]) {
                        if (a[at2[0]] > a[at2[1]]) at2[1] = at2[0];
                        else at2[0] = at2[1];
                    }
                    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;
                    }
                }
                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 + df) {
                            X = at[dir^1];
                            if (a[to[X][dir]] == mx) X = to[X][dir];
                            else X = bst[0][X][dir];
                        }
                    }else{
                        walk(at);
                        if (a[at[dir]] >= mx+df) {
                            X = at[dir];
                        }else{
                            X = at[dir^1];
                            ass(a[X] >= mx + df);
                        }
                    }
                }
            }

//            assert(T[0]<=T[1]);
            int smol = min(a[T[0]], a[T[1]]);
            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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 768 KB Output is correct
2 Correct 29 ms 19448 KB Output is correct
3 Correct 29 ms 19704 KB Output is correct
4 Correct 29 ms 19712 KB Output is correct
5 Correct 29 ms 19576 KB Output is correct
6 Correct 31 ms 19704 KB Output is correct
7 Correct 44 ms 23672 KB Output is correct
8 Correct 29 ms 22412 KB Output is correct
9 Correct 34 ms 22912 KB Output is correct
10 Correct 32 ms 20724 KB Output is correct
11 Correct 38 ms 22996 KB Output is correct
12 Correct 36 ms 21368 KB Output is correct
13 Correct 37 ms 20864 KB Output is correct
14 Correct 38 ms 23032 KB Output is correct
15 Correct 36 ms 21368 KB Output is correct
16 Correct 37 ms 20728 KB Output is correct
17 Correct 32 ms 22264 KB Output is correct
18 Correct 32 ms 22264 KB Output is correct
19 Correct 39 ms 24568 KB Output is correct

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 118 ms 43016 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 225 ms 25328 KB Output is correct
2 Incorrect 224 ms 26988 KB Output isn't correct
3 Halted 0 ms 0 KB -