oj.uz

Submission #72718

# Submission time Handle Problem Language Result Execution time Memory
72718 2018-08-26T20:42:19 Z Benq Railway Trip (JOI17_railway_trip) C++14
100 / 100
 614 ms 89440 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 get(vi& z, int x) {
    return ub(all(z),x)-z.begin();
}

int dist(int x, int y) {
    if (x == y) return 0;
    int t = min(L[x],L[y]);
    return get(tmp[t],y-1)-get(tmp[t],x)+1;
}

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);
    /*cout << ans << " " << A << " " << B << "\n";
    cout << res << " " << L[A] << " " << L[B] << "\n";
    cout << a.f << " " << a.s.f << " " << a.s.s << " " << b.f << " " << b.s.f << " " << b.s.s << "\n";
    cout << L[a.s.f] << " " << L[a.s.s] << " " << L[b.s.f] << " " << L[b.s.s] << "\n";*/
    // cout << ans << " " << a.f << " " << a.s.f << " " << a.s.s << " " << b.f << " " << b.s.f << " " << b.s.s << "\n";
    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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 9336 KB Output is correct
2 Correct 20 ms 9448 KB Output is correct
3 Correct 21 ms 9448 KB Output is correct
4 Correct 25 ms 9448 KB Output is correct
5 Correct 22 ms 9448 KB Output is correct
6 Correct 28 ms 9448 KB Output is correct
7 Correct 19 ms 9448 KB Output is correct
8 Correct 18 ms 9452 KB Output is correct
9 Correct 25 ms 9476 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 9836 KB Output is correct
2 Correct 124 ms 28432 KB Output is correct
3 Correct 158 ms 28516 KB Output is correct
4 Correct 110 ms 28516 KB Output is correct
5 Correct 176 ms 28516 KB Output is correct
6 Correct 183 ms 28516 KB Output is correct
7 Correct 234 ms 29928 KB Output is correct
8 Correct 127 ms 29928 KB Output is correct
9 Correct 142 ms 29928 KB Output is correct
10 Correct 95 ms 29928 KB Output is correct
11 Correct 111 ms 29928 KB Output is correct
12 Correct 115 ms 29928 KB Output is correct
13 Correct 133 ms 29928 KB Output is correct
14 Correct 155 ms 29928 KB Output is correct
15 Correct 116 ms 29928 KB Output is correct
16 Correct 137 ms 29928 KB Output is correct
17 Correct 92 ms 29928 KB Output is correct
18 Correct 96 ms 29928 KB Output is correct
19 Correct 132 ms 30972 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 30972 KB Output is correct
2 Correct 291 ms 30972 KB Output is correct
3 Correct 238 ms 31740 KB Output is correct
4 Correct 228 ms 33188 KB Output is correct
5 Correct 329 ms 34632 KB Output is correct
6 Correct 337 ms 36128 KB Output is correct
7 Correct 284 ms 37372 KB Output is correct
8 Correct 284 ms 38680 KB Output is correct
9 Correct 485 ms 40256 KB Output is correct
10 Correct 447 ms 41512 KB Output is correct
11 Correct 509 ms 43060 KB Output is correct
12 Correct 541 ms 44208 KB Output is correct
13 Correct 614 ms 45552 KB Output is correct
14 Correct 306 ms 46996 KB Output is correct
15 Correct 251 ms 48136 KB Output is correct
16 Correct 322 ms 49472 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 350 ms 50932 KB Output is correct
2 Correct 349 ms 52652 KB Output is correct
3 Correct 326 ms 53116 KB Output is correct
4 Correct 249 ms 55112 KB Output is correct
5 Correct 491 ms 56176 KB Output is correct
6 Correct 404 ms 58308 KB Output is correct
7 Correct 364 ms 60152 KB Output is correct
8 Correct 321 ms 61400 KB Output is correct
9 Correct 414 ms 63588 KB Output is correct
10 Correct 440 ms 65072 KB Output is correct
11 Correct 402 ms 66768 KB Output is correct
12 Correct 464 ms 68796 KB Output is correct
13 Correct 425 ms 70452 KB Output is correct
14 Correct 474 ms 72812 KB Output is correct
15 Correct 458 ms 74856 KB Output is correct
16 Correct 354 ms 77236 KB Output is correct
17 Correct 454 ms 77740 KB Output is correct
18 Correct 338 ms 79488 KB Output is correct
19 Correct 319 ms 81372 KB Output is correct
20 Correct 267 ms 82728 KB Output is correct
21 Correct 217 ms 83572 KB Output is correct
22 Correct 265 ms 85436 KB Output is correct
23 Correct 232 ms 89440 KB Output is correct