제출 #554072

#제출 시각아이디문제언어결과실행 시간메모리
554072Zhora_004밀림 점프 (APIO21_jumps)C++17
컴파일 에러
0 ms0 KiB
#include <iostream> #include <cmath> #include <algorithm> #include <vector> #include <set> #include <unordered_set> #include <queue> #include <deque> #include <string> #include <sstream> #include <iomanip> #include <map> #include <unordered_map> #include <stack> #include <cstdio> #include <climits> #include <tuple> #include <ctime> #include <cstring> #include <numeric> #include <functional> #include <chrono> #include <cassert> #include <bitset> #include <fstream> //#include <bit> //#include <ranges> //#include <numbers> #define sz(a) ((int)((a).size())) // printf("%.10f\n", ans); /*ofstream fout("timeline.out"); ifstream fin("timeline.in");*/ using ll = long long; using namespace std; const ll mod = 998244353; const int N = 2e5 + 5, inf = 1e9; int n, q, a, b, c, d, ans; vector<int> h, dp, nge, pge, ind; vector<vector<int>> go1, go2; void NGE() { stack<int> s; s.push(0); for (int i = 1; i < n; i++) { if (s.empty()) { s.push(i); continue; } while (!s.empty() && h[s.top()] < h[i]) { nge[s.top()] = i; s.pop(); } s.push(i); } while (!s.empty()) { nge[s.top()] = -1; s.pop(); } } void PGE() { stack<int> s; s.push(0); pge[0] = -1; for (int i = 1; i < n; i++) { while (!s.empty() && h[s.top()] < h[i]) s.pop(); if (s.empty()) pge[i] = -1; else pge[i] = s.top(); s.push(i); } } int dfs(int u) { if (dp[u] != inf + 1) return dp[u]; if (c <= u && u <= d) return dp[u] = 0; int r = nge[u]; int ans = inf; if (r != -1) ans = min(ans, dfs(r) + 1); int l = pge[u]; if (l != -1) ans = min(ans, dfs(l) + 1); return dp[u] = ans; } void solve() { /*dp = vector<int>(n, inf + 1); ans = inf; for (int i = a; i <= b; i++) ans = min(ans, dfs(i)); if (ans == inf) ans = -1; cout << ans << "\n";*/ if (h[a] > h[c]) { cout << "-1\n"; return; } int ans = 0, id = a; for (int i = 19; i >= 0; i--) { int u = go1[id][i]; if (u < n && h[u] <= h[c]) { ans += (1 << i); id = u; } } for (int i = 19; i >= 0; i--) { int u = go2[id][i]; if (u < n && h[u] <= h[c]) { ans += (1 << i); id = u; } } if (id == c) cout << ans << "\n"; else cout << "-1\n"; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> q; h = nge = pge = vector<int>(n); ind = vector<int>(n + 1); go1 = go2 = vector<vector<int>>(n, vector<int>(20)); for (int i = 0; i < n; i++) cin >> h[i]; NGE(); PGE(); for (int i = 0; i < n; i++) ind[h[i]] = i; for (int i = n; i >= 1; i--) { int id = ind[i]; int l = pge[id], r = nge[id]; if (l == -1 || r == -1) go1[id][0] = n; else { if (h[l] > h[r]) go1[id][0] = l; else go1[id][0] = r; } for (int j = 1; j < 20; j++) { int u = go1[id][j - 1]; if (u == n) go1[id][j] = n; else go1[id][j] = go1[u][j - 1]; } if (l == -1 && r == -1) go2[id][0] = n; else if (l == -1) go2[id][0] = r; else if (r == -1) go2[id][0] = l; else { if (h[l] < h[r]) go2[id][0] = l; else go2[id][0] = r; } for (int j = 1; j < 20; j++) { int u = go2[id][j - 1]; if (u == n) go2[id][j] = n; else go2[id][j] = go2[u][j - 1]; } } while (q--) { cin >> a >> b >> c >> d; solve(); } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

/usr/bin/ld: /tmp/cc0zU3Hg.o: in function `main':
stub.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccVr6nai.o:jumps.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc0zU3Hg.o: in function `main':
stub.cpp:(.text.startup+0x177): undefined reference to `init(int, std::vector<int, std::allocator<int> >)'
/usr/bin/ld: stub.cpp:(.text.startup+0x1d1): undefined reference to `minimum_jumps(int, int, int, int)'
collect2: error: ld returned 1 exit status