Submission #827960

#	Time	Username	Problem	Language	Result	Execution time	Memory
827960		yeyso	Rainforest Jumps (APIO21_jumps)	C++14	39 / 100	1644 ms	280056 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<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
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);
    }
}
/*
void upd(int i, int val, int lbound, int rbound, int j = 1){
    if(i < lbound || rbound < i){
        return;
    }
    if(lbound == rbound){
        tree[j] = {val};
        return;
    }
    int mid = (lbound + rbound) / 2;
    upd(i, val, lbound, mid, j * 2);
    upd(i, val, mid+1, rbound, j * 2 + 1);
    //tree[j] =min(tree[j * 2], tree[j * 2 + 1]);
    //set<int> m;
    tree[j].clear();
    merge(tree[j * 2].begin(), tree[j * 2].end(), tree[j * 2 + 1].begin(), tree[j * 2 + 1].end(), back_inserter(tree[j]));
    fast[0][j].clear();
    fast[1][j].clear();
    int pl = 0;
    int pr = 0;
    /*for(int x = 0; x < tree[j * 2].size() + tree[j * 2 + 1].size(); x ++){
        tree[j].push_back(
    }
    /*for(int x = 0; x < tree[j].size(); x ++){
        fast[0][tree[j][x]][floor(log2(j))] = 0;
    }
    
    pl = 0;
    pr = 0;
    for(int x = 0; x < tree[j].size(); x ++){
        // If tree[j][x] is in the left subtree
        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 {
            // Otherwise it has to be in the right subtree
            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;
        }
    }
}
*/
 
vector<int> query;
void rangeq(int bound, int ql, int qr, int lbound, int rbound, int j = 1){

    if(j == 1){
        int left = 0;
        int right = rbound;
        int m = (left + right) / 2;
        int idx = 0;
        for (int i = ceil(log2(n)); i >= 0; --i) {
            if(idx + (1 << i) < n){
                if(tree[1][idx + (1 << i)] <= bound){
                    //idx = st1[u][i];
                    idx += (1 << i);
                }
            }
        }
        
        int up = 0;
        int mid = (lbound + rbound) / 2;
        if(bound >= 0) rangeq(fast[0][j][bound], ql, qr, lbound, mid, j * 2);
        if(bound >= 0) rangeq(fast[1][j][bound], ql, qr, mid+1, rbound, j * 2 + 1);
    } else {
        if(qr < lbound || rbound < ql){
            return;
            //return INT_MAX;
            // DONT DO ANYTHING
        } else if(ql <= lbound and rbound <= qr){
            
            //return tree[j];
            if(bound >= 0){
                query.push_back(tree[j][bound]);
            }
            //query.push_back(tree[j][bound]);
            //query.push_back(bound);
            //query.push_back(j);
            return;
    
        } else {
            int mid = (lbound + rbound) / 2;
            if(bound >= 0) rangeq(fast[0][j][bound], ql, qr, lbound, mid, j * 2);
            if(bound >= 0) rangeq(fast[1][j][bound], ql, qr, mid+1, rbound, j * 2 + 1);
        }
    }
    //return min(left_value, right_value);
}
// 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));
    st0 = st;
    st1 = st;
    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);
    /*for(int i = 0; i < st1.size(); i ++){
        for(int j = 0; j < st1[i].size(); j ++){
            cout << h[st1[i][j]] << " ";
        } cout << "\n";
    }*/
 
    //if(A == B and C != D){
    /*for(int i = 0; i < N; i ++){
        upd(i, H[i], 0, N);
    }*/
    build(1, 0, N + 1);
    /*for(int i = 0; i < 20; i ++){
        cout << i << " | ";
        for(int j = 0; j < tree[i].size(); j ++){
            cout << tree[i][j] << " ";
        } cout << "\n";
    }*/
    //}
}
 
int minimum_jumps(int A, int B, int C, int D){
    if(C == D){
        // In this case, our O(logn) algorithm for subtask 5
        query.clear();
        //cout << h[6];
        rangeq(h[C], A, B, 0, n + 1);
        int best = -1;
        for(int i = 0; i < query.size(); i ++){
            //cout << query[i] << " ";
            //if(query[i] <= h[C]){
                best = max(best, query[i]);
            //}
        } //cout << "\n";
        //return best;
        //}
        //cout << best << "\n";
        int jumps = 0;
        int u = 0;
        if(best > 0){
            u = htt[best - 1];
        } else {
            return -1;
        }
        //return u;
        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;
    } else {
        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;
}
/*
g++ -std=gnu++17 -O2 -pipe -o jumps jumps.cpp stub.cpp
 
7 6
3 2 1 6 4 5 7
0 3 4 4
0 4 4 4
0 5 4 4
0 3 5 5
0 4 5 5
0 5 5 5
 
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:76:5: warning: "/*" within comment [-Wcomment]
   76 |     /*for(int x = 0; x < tree[j * 2].size() + tree[j * 2 + 1].size(); x ++){
      |      
jumps.cpp:79:5: warning: "/*" within comment [-Wcomment]
   79 |     /*for(int x = 0; x < tree[j].size(); x ++){
      |      
jumps.cpp: In function 'void build(int, int, int)':
jumps.cpp:38:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         for(int x = 0; x < tree[j].size(); x ++){
      |                        ~~^~~~~~~~~~~~~~~~
jumps.cpp: In function 'void rangeq(int, int, int, int, int, int)':
jumps.cpp:115:13: warning: unused variable 'm' [-Wunused-variable]
  115 |         int m = (left + right) / 2;
      |             ^
jumps.cpp:126:13: warning: unused variable 'up' [-Wunused-variable]
  126 |         int up = 0;
      |             ^~
jumps.cpp: In function 'void dfs0(int, int)':
jumps.cpp:162:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  162 |         for(int i = 0; i < radj[u].size(); i ++){
      |                        ~~^~~~~~~~~~~~~~~~
jumps.cpp:164:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |             for(int j = 0; j < adj[radj[u][i]].size(); j ++){
      |                            ~~^~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp: In function 'void dfs1(int, int)':
jumps.cpp:182:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  182 |         for(int i = 0; i < radj[u].size(); i ++){
      |                        ~~^~~~~~~~~~~~~~~~
jumps.cpp:184:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  184 |             for(int j = 0; j < adj[radj[u][i]].size(); j ++){
      |                            ~~^~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:249:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  249 |     for(int i = 0; i < H.size(); i ++){
      |                    ~~^~~~~~~~~~
jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:282:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  282 |         for(int i = 0; i < query.size(); i ++){
      |                        ~~^~~~~~~~~~~~~~
jumps.cpp:343:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  343 |                     for(int i = 0; i < adj[node].size(); i ++){
      |                                    ~~^~~~~~~~~~~~~~~~~~

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