Submission #828970

#	Time	Username	Problem	Language	Result	Execution time	Memory
828970		yeyso	Rainforest Jumps (APIO21_jumps)	C++14	0 / 100	53 ms	98788 KiB

jumps

    #include "jumps.h"
    #include <bits/stdc++.h>
    using namespace std;
    // st0[u][z] = st0[st0[u][z-1]][z-1];
    #include <vector>
    vector<vector<int>> adj;
    vector<vector<int>> radj;
    int n = 0;
    vector<vector<int>> st0;
    vector<vector<int>> st1;
    vector<int> visited;
    vector<int> h;
    // SEGMENT TREE
    const int S_ = 262144 * 4 + 5;
    vector<vector<int>> tree(S_, vector<int>());
    // fast[l/r][node][number] = biggest element <= number in l/r subtree of node
    // wait NVM
    // For each element inside a segment tree node, we need the O(1) function for that node 
    //vector<vector<map<int, int>>> fast(2, vector<map<int, int>>(262144 * 2 + 5, map<int, int>()));
    // fast[l/r][node][index within that node] = biggest element <= node[index] in l/r subtree of node
    vector<vector<vector<int>>> fast(2, vector<vector<int>>(262144 * 4 + 5, vector<int>()));
    vector<vector<int>> RMQ;
    /*
    THE PLAN

    To find the best tree in the range [A, B]
    - Find the rightmost tree in the range that is taller than C, call it X using a 
    Segtree that supports range rightmost threshold queries! 

    Then a segtree that supports range upper bound queries!
    A != B but C = D



    A ... B 
    Let X = rightmost tree between A and B that is taller than C
    Now use range upper bound to find tallest tree between X and B that is shorter than C

    And then do RMQ(C) for the tree we want to start at
    Then we need to find the fastest way to get to (C -- D)
    Solve the problem in reverse

    - Then do the range upper bound query within the range [X, B]
    */
    //vector<vector<vector<int>>> fast(2, vector<vector<int>>(262144 * 2 + 5, vector<int>()));
    //int[2][262144 * 2 +5][] fast;
    // For each node in the segment tree, we have O(log(n)) numbers
    // n logn + n logn + n logn ... logn times

    int fast_log(int x){
        return x ? __builtin_clzll(1) - __builtin_clzll(x) : -1;
    }
    void build(int j, int tl, int tr) {
        if (tl == tr) {
            tree[j] = {h[tl]};
            return;
        } else {
            int tm = (tl + tr) / 2;
            build(j*2, tl, tm);
            build(j*2+1, tm+1, tr);
            merge(tree[j * 2].begin(), tree[j * 2].end(), tree[j * 2 + 1].begin(), tree[j * 2 + 1].end(), back_inserter(tree[j]));
            int pl = 0;
            int pr = 0;
            
            for(int x = 0; x < tree[j].size(); x ++){
                if(tree[j * 2][pl] == tree[j][x]){
                    fast[0][j].push_back(pl);
                    if(x == 0){ fast[1][j].push_back(-1);
                    } else { fast[1][j].push_back(fast[1][j][fast[1][j].size() - 1]); }
                    pl += 1;
                } else {
                    fast[1][j].push_back(pr);
                    if(x == 0){ fast[0][j].push_back(-1);
                    } else { fast[0][j].push_back(fast[0][j][fast[0][j].size() - 1]); }
                    pr += 1;
                }
            }
    
            if(fast[1][j].size() == 0) fast[1][j].push_back(-1);
            if(fast[0][j].size() == 0) fast[0][j].push_back(-1);
        }
    }
    
    vector<int> query;
    int rmq0(int l, int r){
        int i = fast_log(r - l + 1);
        return max(RMQ[i][l], RMQ[i][r - (1 << i) + 1]);
    }
    int qu = 0;
    void rightmost(int threshold, int ql, int qr, int lbound, int rbound, int j = 1){
        int mid = (lbound + rbound) / 2;
        if(lbound == rbound){
            qu = max(qu, lbound);
            return;
        }
        int call = 0;
        if(rmq0(mid+1, rbound) >= threshold){
            if(ql <= rbound and qr >= mid + 1){
                call = 1;
                rightmost(threshold, ql, qr, mid+1, rbound, j * 2 + 1);
            }
        }
        if(rmq0(lbound, mid) >= threshold){
            if(!call){
                if(ql <= mid and qr >= lbound){
                    rightmost(threshold, ql, qr, lbound, mid, j * 2);
                }
            }
        }
    }
    void rangeq(int bound, int ql, int qr, int lbound, int rbound, int j = 1){
        if(qr < lbound || rbound < ql){
            //return INT_MAX;
            // DONT DO ANYTHING
        } else if(ql <= lbound and rbound <= qr){
            if(bound >= 0){
                query.push_back(tree[j][bound]);
            }
        } else {
            int mid = (lbound + rbound) / 2;
            if(bound >= 0){
                rangeq(fast[0][j][bound], ql, qr, lbound, mid, j * 2);
                rangeq(fast[1][j][bound], ql, qr, mid+1, rbound, j * 2 + 1);
            }
        }
    }
    // Construct sparse tables
    void dfs0(int u, int v){
        if(!visited[u]){
            visited[u] = 1;
            st0[u][0] = v;
            for(int z = 1; z <= ceil(log2(n)); z ++){
                st0[u][z] = st0[st0[u][z-1]][z-1];
            }
            for(int i = 0; i < radj[u].size(); i ++){
                int highedge = 1;
                for(int j = 0; j < adj[radj[u][i]].size(); j ++){
                    if(h[adj[radj[u][i]][j]] > h[u]){
                        highedge = 0;
                    }
                }
                if(highedge){
                    dfs0(radj[u][i], u);
                }
            }
        }
    }
    void dfs1(int u, int v){
        if(!visited[u]){
            visited[u] = 1;
            st1[u][0] = v;
            for(int z = 1; z <= ceil(log2(n)); z ++){
                st1[u][z] = st1[st1[u][z-1]][z-1];
            }
            for(int i = 0; i < radj[u].size(); i ++){
                int lowedge = 1;
                for(int j = 0; j < adj[radj[u][i]].size(); j ++){
                    if(h[adj[radj[u][i]][j]] < h[u]){
                        lowedge = 0;
                    }
                }
                if(lowedge){
                    dfs1(radj[u][i], u);
                }
            }
        }
    }
        
    int subtask1 = 1;
    vector<int> htt;
    void init(int N, vector<int> H) {
        n = N;
        h = H;
        stack<pair<int, int>> s;
        vector<vector<int>> adj0(N, vector<int>());
        int highest = 0;
        int idx = 0;
        vector<vector<int>> radj0(N, vector<int>());
        // Monotonic stack to construct adjacency list in O(n)
        for (int i = 0; i < N; i ++) {
            if(i > 0){
                if(H[i] != i + 1){
                    subtask1 = 0;
                }
            }
            while (!s.empty() && s.top().first < H[i]){ s.pop(); }
            if (!s.empty()){
                adj0[i].push_back(s.top().second);
                radj0[s.top().second].push_back(i);
            }
            s.push({H[i], i});
            if(H[i] > highest){
                highest = H[i];
                idx = i;
            }
        }
        while(!s.empty()){ s.pop(); }
        for (int i = N - 1; i >= 0; i --) {
            while (!s.empty() && s.top().first < H[i]){ s.pop(); }
            if (!s.empty()){
                adj0[i].push_back(s.top().second);
                radj0[s.top().second].push_back(i);
            }
            s.push({H[i], i});
        }
        adj = adj0;
        radj = radj0;
        vector<vector<int>> st(N, vector<int>(ceil(log2(n)) + 1, 0));
        vector<vector<int>> rmqt(ceil(log2(n))+1, vector<int>(N, 0));
        st0 = st;
        st1 = st;
        RMQ = rmqt;
        for(int j = 0; j < n; j ++){
            RMQ[0][j] = H[j];
        }
        for(int i = 1; i <= ceil(log2(n)); i ++){
            for(int j = 0; j < n; j ++){
                RMQ[i][j] = max(RMQ[i-1][j], RMQ[i-1][j + (1 << (i - 1))]);
            }
        }
        vector<int> v(N, 0);
        visited = v;
        htt = v;
        for(int i = 0; i < H.size(); i ++){
            htt[H[i] - 1] = i;
        }
        dfs0(idx, idx);
        visited = v;
        dfs1(idx, idx);
        build(1, 0, N + 1);
    }
    
    int minimum_jumps(int A, int B, int C, int D){
        qu = -1;
        rightmost(h[C], A, B, 0, n);
        return qu;
        //return rmq0(A, B);
        int start = 0;
        if(qu != -1 and qu < B){
            start = rmq0(qu + 1, B);
        } else {
            start = rmq0(A, B);
        }
        //int start = rmq0(max(qu+1, A), B);
        //return qu;
        
        /*if(C == D){
            int jumps = 0;
            int u = htt[start - 1];
            for (int i = ceil(log2(n)); i >= 0; --i) {
                if(h[st0[u][i]] < h[C]){
                    u = st0[u][i];
                    jumps += (1 << i);
                }
            }
            // If the first sparse table is all we need, we're done
            if(st0[u][0] == C){
                return jumps + 1;
            } else {
                // Otherwise start at the next sparse table
                for (int i = ceil(log2(n)); i >= 0; --i) {
                    if(h[st1[u][i]] < h[C]){
                        u = st1[u][i];
                        jumps += (1 << i);
                    }
                }
                
                if(st1[u][0] == C){
                    return jumps + 1;
                }
            }
            return -1;
        }  *//*{
            if(subtask1){
                return C - B;
            } else {
                queue<pair<int, int>> q;
                for(int i = A; i <= B; i ++){
                    q.push({0, i});
                }
                int node = 0; int dist = 0;
                vector<int> vi(n, 0);
                while(!q.empty()){
                    node = q.front().second;
                    dist = q.front().first;
                    //cout << node << "\n";
                    q.pop();
                    if(node >= C && node <= D){
                        return dist;
                        //break;
                    }
                    if(!vi[node]){
                        vi[node] = 1;
                        for(int i = 0; i < adj[node].size(); i ++){
                            q.push({dist + 1, adj[node][i]});
                        }
                    }
                }
    
                return -1;
            }
        }*/
        return -1;
        
    }
    /*
    The rightmost tree within range that is taller than 
    g++ -std=gnu++17 -O2 -pipe -o jumps jumps.cpp stub.cpp

7 3
3 7 5 6 4 2 1
0 1 6 6
0 2 6 6
0 3 6 6
0 4 4 4
0 5 4 4
0 6 4 4
3 6 5 5
4 6 5 5
5 6 5 5
6 6 6 6
    
    if(A == B and C == D){
            int jumps = 0;
            int u = A;
            for (int i = ceil(log2(n)); i >= 0; --i) {
                if(h[st0[u][i]] < h[C]){
                    u = st0[u][i];
                    jumps += (1 << i);
                }
            }
            // If the first sparse table is all we need, we're done
            if(st0[u][0] == C){
                return jumps + 1;
            } else {
                // Otherwise start at the next sparse table
            for (int i = ceil(log2(n)); i >= 0; --i) {
                    if(h[st1[u][i]] < h[C]){
                        u = st1[u][i];
                        jumps += (1 << i);
                    }
                }
        
                if(st1[u][0] == C){
                    return jumps + 1;
                }
            }
            return -1;
        // Otherwise, if it's subtask 1, we do our dumb solution
        } else if(subtask1){
            return C - B;
        // Subtask 6 - wavelet tree
        } else if(C == D){
            cout << 100;
            query.clear();
            //rangeq(C, A, B, 0, n);
    
            for(int i = 0; i < query.size(); i ++){
                cout << query[i] << " ";
            } cout << "\n";
    
    
            // Now it's only subtask 2, 3 or 4 so we do BFS
        } else {
            //return u;
        if(jumps){
            return jumps + 1;
        } else {
            return 0;
        }
            queue<pair<int, int>> q;
            for(int i = A; i <= B; i ++){
                q.push({0, i});
            }
            int node = 0; int dist = 0;
            vector<int> vi(n, 0);
            while(!q.empty()){
                node = q.front().second;
                dist = q.front().first;
                //cout << node << "\n";
                q.pop();    x   
                if(node >= C && node <= D){
                    return dist;
                    //break;
                }
                if(!vi[node]){
                    vi[node] = 1;
                    for(int i = 0; i < adj[node].size(); i ++){
                        q.push({dist + 1, adj[node][i]});
                    }
                }
            }
    
            return -1;
        }
    */

Compilation message (stderr)

jumps.cpp: In function 'void build(int, int, int)':
jumps.cpp:65:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |             for(int x = 0; x < tree[j].size(); x ++){
      |                            ~~^~~~~~~~~~~~~~~~
jumps.cpp: In function 'void dfs0(int, int)':
jumps.cpp:135:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |             for(int i = 0; i < radj[u].size(); i ++){
      |                            ~~^~~~~~~~~~~~~~~~
jumps.cpp:137:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |                 for(int j = 0; j < adj[radj[u][i]].size(); j ++){
      |                                ~~^~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp: In function 'void dfs1(int, int)':
jumps.cpp:155:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |             for(int i = 0; i < radj[u].size(); i ++){
      |                            ~~^~~~~~~~~~~~~~~~
jumps.cpp:157:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |                 for(int j = 0; j < adj[radj[u][i]].size(); j ++){
      |                                ~~^~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:224:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  224 |         for(int i = 0; i < H.size(); i ++){
      |                        ~~^~~~~~~~~~
jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:238:13: warning: variable 'start' set but not used [-Wunused-but-set-variable]
  238 |         int start = 0;
      |             ^~~~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19