답안 #304139

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
304139 2020-09-21T03:22:29 Z Kevin_Zhang_TW Railway Trip (JOI17_railway_trip) C++17
20 / 100
227 ms 25324 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); }
#define assert(...) 0
#define ass(...) 0
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
*/

Compilation message

railway_trip.cpp:106: warning: "assert" redefined
  106 | #define assert(...) 0
      | 
In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from railway_trip.cpp:1:
/usr/include/assert.h:88: note: this is the location of the previous definition
   88 | # define assert(expr)       \
      |
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 768 KB Output is correct
2 Correct 27 ms 19448 KB Output is correct
3 Correct 28 ms 19448 KB Output is correct
4 Correct 28 ms 19200 KB Output is correct
5 Correct 28 ms 19320 KB Output is correct
6 Correct 30 ms 19320 KB Output is correct
7 Correct 42 ms 23032 KB Output is correct
8 Correct 26 ms 22268 KB Output is correct
9 Correct 33 ms 22264 KB Output is correct
10 Correct 29 ms 20212 KB Output is correct
11 Correct 36 ms 22392 KB Output is correct
12 Correct 33 ms 20728 KB Output is correct
13 Correct 33 ms 20216 KB Output is correct
14 Correct 35 ms 22400 KB Output is correct
15 Correct 34 ms 20736 KB Output is correct
16 Correct 35 ms 20216 KB Output is correct
17 Correct 31 ms 21624 KB Output is correct
18 Correct 31 ms 21632 KB Output is correct
19 Correct 35 ms 23928 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 209 ms 21768 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 213 ms 25324 KB Output is correct
2 Incorrect 227 ms 25320 KB Output isn't correct
3 Halted 0 ms 0 KB -