oj.uz

답안 #72717

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
72717 2018-08-26T20:33:01 Z Benq Railway Trip (JOI17_railway_trip) C++14
0 / 100
 464 ms 30224 KB 
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/rope>

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

template<class T, int SZ> struct RMQ {
    T stor[SZ][32-__builtin_clz(SZ)];
    
    T comb(T a, T b) {
        return max(a,b);
    }
    
    void build() {
        FOR(j,1,32-__builtin_clz(SZ)) F0R(i,SZ-(1<<(j-1))) 
            stor[i][j] = comb(stor[i][j-1],
                        stor[i+(1<<(j-1))][j-1]);
    }
    
    T query(int l, int r) {
        int x = 31-__builtin_clz(r-l+1);
        return comb(stor[l][x],stor[r-(1<<x)+1][x]);
    }
};

RMQ<int,MX> R;

int N,K,Q,L[MX];
pi bound[MX][17];
vi tmp[MX];
set<int> S;

pi nex(pi x, int y) {
    return {min(bound[x.f][y].f,bound[x.s][y].f),
            max(bound[x.f][y].s,bound[x.s][y].s)};
}

int dist(int x, int y) {
    if (L[x] != L[y]) return 1;
    // cout << "ZZ " << x << " " << y << "\n";
    return distance(find(all(tmp[L[x]]),x),find(all(tmp[L[x]]),y));
}

pair<int,pi> tri(int x, int y) {
    int num = 0; pi cur = {x,x};
    
    F0Rd(i,17) {
        pi CUR = nex(cur,i);
        if (max(L[CUR.f],L[CUR.s]) < y) {
            cur = CUR;
            num ^= 1<<i;
        }
    }
    if (max(L[cur.f],L[cur.s]) < y) {
        cur = nex(cur,0);
        num ++;
    }
    
    return {num,cur};
}

int solve(int A, int B) {
    int res = R.query(A,B);
    
    pair<int,pi> a = tri(A,res), b = tri(B,res); // first time you to at least that level 
    
    int ans = a.f+b.f+dist(L[a.s.s] >= res ? a.s.s : a.s.f,L[b.s.f] >= res ? b.s.f : b.s.s);
    if (res != K) {
        a = tri(A,res+1), b = tri(B,res+1); 
        if (a.s.f == b.s.f || a.s.s == b.s.s) ans = min(ans,a.f+b.f);
        else ans = min(ans,a.f+b.f+1);
    }
    
    return ans;
}

void init() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N >> K >> Q;
    FOR(i,1,N+1) {
        cin >> L[i];
        R.stor[i][0] = L[i];
        tmp[L[i]].pb(i);
    }
    R.build();
    FORd(i,1,K+1) {
        sort(all(tmp[i]));
        for (int j: tmp[i]) S.insert(j);
        for (int j: tmp[i]) {
            auto it = S.find(j);
            bound[j][0].f = (it == S.begin() ? 1 : *prev(it));
            bound[j][0].s = (next(it) == S.end() ? N : *next(it));
        }
    }
    F0R(j,16) FOR(i,1,N+1) bound[i][j+1] = nex(bound[i][j],j);
}

int main() {
    init();
    F0R(i,Q) {
        int A,B; cin >> A >> B;
        if (A > B) swap(A,B);
        cout << solve(A,B)-1 << "\n";
    }
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
* if you have no idea just guess the appropriate well-known algo instead of doing nothing :/
*/

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 9336 KB Output is correct
2 Correct 19 ms 9476 KB Output is correct
3 Incorrect 19 ms 9476 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 20 ms 9636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 464 ms 28916 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 257 ms 30224 KB Output isn't correct
2 Halted 0 ms 0 KB -