Submission #1201145

#TimeUsernameProblemLanguageResultExecution timeMemory
1201145guagua0407Rainforest Jumps (APIO21_jumps)C++20
Compilation error
0 ms0 KiB
#include<bits/stdc++.h> using namespace std; //#include "jumps.h" #include "stub.cpp" #define F first #define S second #define double long double #define all(x) x.begin(),x.end() #define pii pair<int,int> #define pb push_back #define sz(x) (int)(x.size()) #define vi vector<int> #define vp vector<pii> #define vvi vector<vi> #define ykh mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()) namespace{ const int mxn = 2e5 + 5; int l[mxn],r[mxn]; int n, h[mxn], o[20][mxn], R[20][mxn]; int chmax(int a,int b){ return (h[a]>h[b]?a:b); } } void init(int N, std::vector<int> H) { n = N; h[0] = 2e9, h[n + 1] = 2e9; for(int i = 1; i <= n; i++){ h[i] = H[i - 1]; } vector<int>st; st.pb(0); for(int i = 1; i <= n ; i++){ while(sz(st) and h[st.back()] < h[i]) st.pop_back(); l[i] = st.back(); st.pb(i); } st.clear(); st.pb(n + 1); R[0][n + 1] = n + 1; o[0][n + 1] = n + 1; for(int i = n ; i > 0; i--){ while(sz(st) and h[st.back()] < h[i]) st.pop_back(); r[i] = st.back(); st.pb(i); } for(int j=0;j<=n;j++){ o[0][j]=chmax(l[j],r[j]); R[0][j]=r[j]; } for(int i = 1; i < 20; i++){ for(int j = 0; j <= n + 1; j++){ o[i][j] = chmax(o[i-1][o[i-1][j]], o[i-1][o[i-1][j]]); R[i][j] = R[i-1][R[i-1][j]]; //cout << i << ' ' << j << ' ' << l[i][j] << ' ' << r[i][j] << '\n'; } } } int minimum_jumps(int A, int B, int C, int D) { A++, B++, C++, D++; int mn=1e9; for(int t=A;t<=B;t++){ int ans = 0; int x=t; for(int i = 19; i >= 0; i--){ int y=o[i][x]; //cout << nl << ' ' << nr << '\n'; if(h[y] < h[C]){ ans += (1 << i); x=y; //cout<<L<<' '<<R<<'\n'; } } //cout<<L<<' '<<R<<'\n'; for(int i = 19; i >= 0; i--){ int y=R[i][x]; //cout << nl << ' ' << nr << '\n'; if(h[y] < h[C]){ ans += (1 << i); x=y; } } //cout << r[0][R] << ' ' << r[0][L] << '\n';; if(r[x]>=C and r[x]<=D){ mn=min(mn,ans+1); } } return (mn==1e9?-1:mn); } /* 6 1 5 1 2 3 4 6 1 1 4 4 */

Compilation message (stderr)

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