Submission #981577

#TimeUsernameProblemLanguageResultExecution timeMemory
981577Ghulam_JunaidRainforest Jumps (APIO21_jumps)C++17
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> #include "grader.cpp" using namespace std; const int MXN = 2e5 + 10; const int T = 330; int n, pos[MXN], to_left[MXN], to_right[MXN], dp[MXN][T + 1]; vector<int> seg[4 * MXN], h; bool subtask1 = 1; void build(int v = 1, int s = 0, int e = n){ if (e - s == 1){ seg[v] = {h[s]}; return; } int mid = (s + e) / 2, lc = 2 * v, rc = lc + 1; build(lc, s, mid); build(rc, mid, e); seg[v] = seg[lc]; for (int x : seg[rc]) seg[v].push_back(x); sort(seg[v].begin(), seg[v].end()); } int get(int l, int r, int x, int v = 1, int s = 0, int e = n){ // int mx = -1; // for (int i = l; i < r; i ++) // if (h[i] < x) // mx = max(mx, h[i]); // return mx; if (e <= l || r <= s) return -1; if (l <= s && e <= r){ if (x > seg[v].back()) return seg[v].back(); if (x <= seg[v][0]) return -1; int lb = lower_bound(seg[v].begin(), seg[v].end(), x) - seg[v].begin(); return seg[v][lb - 1]; } int mid = (s + e) / 2, lc = 2 * v, rc = lc + 1; return max(get(l, r, x, lc, s, mid), get(l, r, x, rc, mid, e)); } void init(int N, vector<int> H) { n = N; h = H; for (int i = 0; i < n; i ++) pos[h[i]] = i, subtask1 &= (h[i] == (i + 1)); build(); stack<int> S; for (int i = 0; i < n; i ++){ while(S.size() and h[S.top()] <= h[i]) S.pop(); if (S.size()) to_left[i] = S.top(); else to_left[i] = i; S.push(i); } while (S.size()) S.pop(); for (int i = n - 1; i >= 0; i --){ while (S.size() and h[S.top()] <= h[i]) S.pop(); if (S.size()) to_right[i] = S.top(); else to_right[i] = i; S.push(i); } // for (int i = 0; i < n; i ++){ // to_left[i] = to_right[i] = i; // for (int j = i + 1; j < n; j ++){ // if (h[j] > h[i]){ // to_right[i] = j; // break; // } // } // for (int j = i - 1; j >= 0; j --){ // if (h[j] > h[i]){ // to_left[i] = j; // break; // } // } // } for (int i = 0; i < n; i ++){ dp[i][0] = i; for (int j = 1; j <= T; j ++){ dp[i][j] = (h[to_left[dp[i][j - 1]]] > h[to_right[dp[i][j - 1]]]) ? to_left[dp[i][j - 1]] : to_right[dp[i][j - 1]]; } } } int minimum_jumps(int A, int B, int C, int D) { if (subtask1) return C - B; B++, D++; int mx = get(C, D, n + 1); int l = A - 1, r = B - 1; if (get(r, C, n + 1) > mx) return -1; while (r - l > 1){ int mid = (l + r) / 2; if (get(mid, C, n + 1) > mx) l = mid; else r = mid; } int val = get(r, B, mx); if (val == -1) return -1; int st = pos[val]; if (get(st, C, n + 1) > mx) return -1; int ope = 0; if (C + 1 == D){ while (h[dp[st][T]] < h[C]){ st = dp[st][T]; ope += T; } while (st < C){ st = to_right[st]; ope++; } } else{ while (st < C){ ope++; int opt1 = to_left[st]; int opt2 = to_right[st]; if (opt2 >= C or h[opt2] > h[opt1] or h[opt1] > mx) st = opt2; else st = opt1; } } return ope; }

Compilation message (stderr)

jumps.cpp:2:10: fatal error: grader.cpp: No such file or directory
    2 | #include "grader.cpp"
      |          ^~~~~~~~~~~~
compilation terminated.