Submission #1204059

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204059		jasonic	Rainforest Jumps (APIO21_jumps)	C++20	Compilation error	0 ms	0 KiB

jumps

#define ll long long
#define fastIO cin.tie(0); ios::sync_with_stdio(false)

int n;
int l[200005];
int r[200005];

struct Element{
    int idx, val;

    Element(): val(-1), idx(-1) {};
    Element(int a, int b): val(a), idx(b) {};

    bool operator<(const Element &b) const {
        return val < b.val;
    }

    bool operator>(const Element &b) const {
        return val > b.val;
    }
};

struct SegTree{
    int l, r;
    int mn, mx;
    Element maxEl;
    SegTree *lt, *rt;

    void comb() {
        mn = min(lt->mn, rt->mn);
        mx = max(lt->mx, rt->mx);
        maxEl = max(lt->maxEl, rt->maxEl);
    }

    SegTree(): l(0), r(0), mn(0), mx(0), lt(nullptr), rt(nullptr) {};
    
    SegTree(int bl, int br, vector<Element> &a) {
        l = bl; r = br;
        lt = rt = nullptr;
        mx = -1;
        mn = n;

        if(l == r) {
            maxEl = a[l];
        } else {
            int m = l + (r-l)/2;
            lt = new SegTree(l, m, a);
            rt = new SegTree(m+1, r, a);
            comb();
        }
    }

    void upd(int i) {
        if(i < l || r < i) return;
        if(i == l && l == r) {
            mn = mx = i;
        } else {
            lt->upd(i);
            rt->upd(i);
            comb();
        }
    }

    int qryMx(int ql, int qr) {
        if(qr < l || r < ql) return -1;
        if(ql <= l && r <= qr) return mx;
        else return max(lt->qryMx(ql, qr), rt->qryMx(ql, qr));
    }

    int qryMn(int ql, int qr) {
        if(qr < l || r < ql) return n;
        if(ql <= l && r <= qr) return mn;
        else return min(lt->qryMn(ql, qr), rt->qryMn(ql, qr));
    }

    Element starting(int ql, int qr) {
        if(qr < l || r < ql) return Element();
        if(ql <= l && r <= qr) return maxEl;
        else return max(lt->starting(ql, qr), rt->starting(ql, qr));
    }
};

SegTree segtree;
unordered_map<int, vector<int>> adjList;

void connect(int x, int y) {
    adjList[x].push_back(y);
}

void init(int N, int h[]) {
    n = N;
    set<int> process_idx;
    vector<Element> a;
    for(int i = 0; i < n; i++) {
        a.push_back(Element(h[i], i));
    }
    segtree = SegTree(0, n-1, a);

    sort(a.begin(), a.end(), greater());
    for(int i = 0; i < n; i++) {
        l[a[i].idx] = segtree.qryMx(0, max(a[i].idx, 0));
        r[a[i].idx] = segtree.qryMn(min(a[i].idx, n-1), n-1);
        segtree.upd(a[i].idx);
        int x = a[i].idx;
        int y = l[a[i].idx];
        int z = r[a[i].idx];
        if(y>=0) connect(x, y);
        if(z<=n-1) connect(x, z);
    }
}

int minimum_jumps(int a, int b, int c, int d) {
    vector<int> dist(n, -1);
    queue<int> bfs;
    for(int i = a; i <= b; i++) {
        dist[i] = 0;
        bfs.push(i);
    }
    while(!bfs.empty()) {
        int curr = bfs.front(); bfs.pop();
        if(c <= curr && curr <= d) return dist[curr];

        for(auto i : adjList[curr]) {
            if(dist[i] != -1) continue;
            dist[i] = dist[curr] + 1;
            bfs.push(i);
        }
    }
    return -1;
}

Compilation message (stderr)

jumps.cpp:38:29: error: 'vector' has not been declared
   38 |     SegTree(int bl, int br, vector<Element> &a) {
      |                             ^~~~~~
jumps.cpp:38:35: error: expected ',' or '...' before '<' token
   38 |     SegTree(int bl, int br, vector<Element> &a) {
      |                                   ^
jumps.cpp: In member function 'void SegTree::comb()':
jumps.cpp:31:14: error: 'min' was not declared in this scope; did you mean 'mn'?
   31 |         mn = min(lt->mn, rt->mn);
      |              ^~~
      |              mn
jumps.cpp:32:14: error: 'max' was not declared in this scope; did you mean 'mx'?
   32 |         mx = max(lt->mx, rt->mx);
      |              ^~~
      |              mx
jumps.cpp: In constructor 'SegTree::SegTree(int, int, int)':
jumps.cpp:45:21: error: 'a' was not declared in this scope
   45 |             maxEl = a[l];
      |                     ^
jumps.cpp:48:36: error: 'a' was not declared in this scope
   48 |             lt = new SegTree(l, m, a);
      |                                    ^
jumps.cpp: In member function 'int SegTree::qryMx(int, int)':
jumps.cpp:68:21: error: 'max' was not declared in this scope; did you mean 'mx'?
   68 |         else return max(lt->qryMx(ql, qr), rt->qryMx(ql, qr));
      |                     ^~~
      |                     mx
jumps.cpp: In member function 'int SegTree::qryMn(int, int)':
jumps.cpp:74:21: error: 'min' was not declared in this scope; did you mean 'mn'?
   74 |         else return min(lt->qryMn(ql, qr), rt->qryMn(ql, qr));
      |                     ^~~
      |                     mn
jumps.cpp: In member function 'Element SegTree::starting(int, int)':
jumps.cpp:80:21: error: 'max' was not declared in this scope; did you mean 'mx'?
   80 |         else return max(lt->starting(ql, qr), rt->starting(ql, qr));
      |                     ^~~
      |                     mx
jumps.cpp: At global scope:
jumps.cpp:85:20: error: 'vector' was not declared in this scope
   85 | unordered_map<int, vector<int>> adjList;
      |                    ^~~~~~
jumps.cpp:85:20: error: 'vector' was not declared in this scope
jumps.cpp:85:20: error: 'vector' was not declared in this scope
jumps.cpp:85:20: error: 'vector' was not declared in this scope
jumps.cpp:85:20: error: 'vector' was not declared in this scope
jumps.cpp:85:20: error: 'vector' was not declared in this scope
jumps.cpp:85:20: error: 'vector' was not declared in this scope
jumps.cpp:85:20: error: 'vector' was not declared in this scope
jumps.cpp:85:20: error: 'vector' was not declared in this scope
jumps.cpp:85:1: error: 'unordered_map' does not name a type
   85 | unordered_map<int, vector<int>> adjList;
      | ^~~~~~~~~~~~~
jumps.cpp: In function 'void connect(int, int)':
jumps.cpp:88:5: error: 'adjList' was not declared in this scope
   88 |     adjList[x].push_back(y);
      |     ^~~~~~~
jumps.cpp: In function 'void init(int, int*)':
jumps.cpp:93:5: error: 'set' was not declared in this scope
   93 |     set<int> process_idx;
      |     ^~~
jumps.cpp:93:9: error: expected primary-expression before 'int'
   93 |     set<int> process_idx;
      |         ^~~
jumps.cpp:94:5: error: 'vector' was not declared in this scope
   94 |     vector<Element> a;
      |     ^~~~~~
jumps.cpp:94:19: error: expected primary-expression before '>' token
   94 |     vector<Element> a;
      |                   ^
jumps.cpp:94:21: error: 'a' was not declared in this scope
   94 |     vector<Element> a;
      |                     ^
jumps.cpp:100:30: error: 'greater' was not declared in this scope
  100 |     sort(a.begin(), a.end(), greater());
      |                              ^~~~~~~
jumps.cpp:100:5: error: 'sort' was not declared in this scope; did you mean 'short'?
  100 |     sort(a.begin(), a.end(), greater());
      |     ^~~~
      |     short
jumps.cpp:102:40: error: 'max' was not declared in this scope
  102 |         l[a[i].idx] = segtree.qryMx(0, max(a[i].idx, 0));
      |                                        ^~~
jumps.cpp:103:37: error: 'min' was not declared in this scope
  103 |         r[a[i].idx] = segtree.qryMn(min(a[i].idx, n-1), n-1);
      |                                     ^~~
jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:114:5: error: 'vector' was not declared in this scope
  114 |     vector<int> dist(n, -1);
      |     ^~~~~~
jumps.cpp:114:12: error: expected primary-expression before 'int'
  114 |     vector<int> dist(n, -1);
      |            ^~~
jumps.cpp:115:5: error: 'queue' was not declared in this scope
  115 |     queue<int> bfs;
      |     ^~~~~
jumps.cpp:115:11: error: expected primary-expression before 'int'
  115 |     queue<int> bfs;
      |           ^~~
jumps.cpp:117:9: error: 'dist' was not declared in this scope
  117 |         dist[i] = 0;
      |         ^~~~
jumps.cpp:118:9: error: 'bfs' was not declared in this scope
  118 |         bfs.push(i);
      |         ^~~
jumps.cpp:120:12: error: 'bfs' was not declared in this scope
  120 |     while(!bfs.empty()) {
      |            ^~~
jumps.cpp:122:43: error: 'dist' was not declared in this scope
  122 |         if(c <= curr && curr <= d) return dist[curr];
      |                                           ^~~~
jumps.cpp:124:22: error: 'adjList' was not declared in this scope
  124 |         for(auto i : adjList[curr]) {
      |                      ^~~~~~~
jumps.cpp:125:16: error: 'dist' was not declared in this scope
  125 |             if(dist[i] != -1) continue;
      |                ^~~~
jumps.cpp:126:13: error: 'dist' was not declared in this scope
  126 |             dist[i] = dist[curr] + 1;
      |             ^~~~