제출 #718686

#제출 시각아이디문제언어결과실행 시간메모리
718686lam밀림 점프 (APIO21_jumps)C++14
컴파일 에러
0 ms0 KiB
#include "jumps.h" #include <cassert> #include <cstdio> #include <vector> #include "jumps.h" #include <bits/stdc++.h> #include <vector> using namespace std; const int maxn = 2e5 + 10; int n; int a[maxn],b[maxn],d[maxn]; vector <int> adj[maxn]; int par[20][maxn]; int f[20][maxn],g[20][maxn]; void create() { for (int i=0; i<n; i++) f[0][i] = b[i]; for (int j=1; (1<<j)<=n; j++) for (int i=0; i+(1<<j)-1<n; i++) f[j][i] = max(f[j-1][i],f[j-1][i+(1<<(j-1))]); } int get(int l, int r) { if (l>r) return -1; int k=log2(r-l+1); return max(f[k][l],f[k][r-(1<<k)+1]); } void addedge(int u, int v) { adj[u].push_back(v); } void init(int N, std::vector<int> H) { n=N; for (int i=0; i<n; i++) a[i]=H[i],adj[i].clear(); deque<int> dq; for (int i=n-1; i>=0; i--) { while (!dq.empty()&&a[dq.back()] < a[i]) dq.pop_back(); if (!dq.empty()) b[i] = dq.back(), d[i]=d[dq.back()]+1; else b[i] = -1,d[i]=0; dq.push_back(i); } while (!dq.empty()) dq.pop_back(); for (int i=0; i<n; i++) { while (!dq.empty()&&a[dq.back()] < a[i]) dq.pop_back(); if (!dq.empty()) par[0][i] = dq.back(), g[0][i] = d[i]; else par[0][i]=-1, g[0][i] = -1e9; dq.push_back(i); } create(); for (int i=0; i<n; i++) for (int j=1; j<20; j++) if (par[j-1][i]==-1) par[j][i]=-1,g[j][i] = -1e9; else { par[j][i]=par[j-1][par[j-1][i]]; g[j][i] = max(g[j-1][i],g[j-1][par[j-1][i]]); } } int minimum_jumps(int A, int B, int C, int D) { if (A==C) return 0; if (a[A] > a[C]) return -1; int smx = get(B+1,C-1); if (smx > a[C]) return -1; int ans = 1e9; if (smx < a[C]) ans = d[A] - d[C]; int u=A; for (int i=19; i>=0; i--) if (par[i][u]!=-1&&a[par[i][u]] < a[C]) { ans = min(ans,g[i][u]-d[C]); u=par[i][u]; } return ans; } int main() { int N, Q; assert(2 == scanf("%d %d", &N, &Q)); std::vector<int> H(N); for (int i = 0; i < N; ++i) { assert(1 == scanf("%d", &H[i])); } init(N, H); for (int i = 0; i < Q; ++i) { int A, B, C, D; assert(4 == scanf("%d %d %d %d", &A, &B, &C, &D)); printf("%d\n", minimum_jumps(A, B, C, D)); } return 0; }

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

/usr/bin/ld: /tmp/ccemYm0O.o: in function `main':
stub.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccou44uQ.o:jumps.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status