제출 #860206

#제출 시각아이디문제언어결과실행 시간메모리
860206nnhzzz밀림 점프 (APIO21_jumps)C++14
4 / 100
927 ms50220 KiB
// cre: Nguyen Ngoc Hung - Train VOI 2024 :> #include <algorithm> #include <bitset> #include <complex> #include <deque> #include <exception> #include <fstream> #include <functional> #include <iomanip> #include <ios> #include <iosfwd> #include <iostream> #include <istream> #include <iterator> #include <limits> #include <list> #include <locale> #include <map> #include <memory> #include <new> #include <numeric> #include <ostream> #include <queue> #include <set> #include <unordered_set> #include <sstream> #include <stack> #include <stdexcept> #include <streambuf> #include <string> #include <typeinfo> #include <utility> #include <valarray> #include <vector> #include <cstring> #include <unordered_map> #include <cmath> #include <array> #include <cassert> #include <random> using namespace std; #define __nnhzzz__ signed main() #define BIT(i,j) ((i>>j)&1LL) #define MASK(i) (1LL<<i) #define ALL(x) (x).begin(),(x).end() #define SZ(x) (int)(x).size() #define fi first #define se second #define ll long long #define vi vector<int> #define vvi vector<vi> #define pii pair<int,int> #define vpii vector<pii> #define REPDIS(i,be,en,j) for(int i = (be); i<=(en); i+=j) #define REPD(i,be,en) for(int i = (be); i>=(en); i--) #define REP(i,be,en) for(int i = (be); i<=(en); i++) //-------------------------------------------------------------// const int oo = 1e9,LOG = 18,MAXN = 5e5+7,N = 1e2+3; const int MOD = 1e9+7,MOD1 = 1e9+207,MOD2 = 1e9+407,MOD3 = 998244353; //-------------------------------------------------------------// template<typename T1, typename T2> bool mini(T1 &a, T2 b){if(a>b){a=b;return true;}return false;} template<typename T1, typename T2> bool maxi(T1 &a, T2 b){if(a<b){a=b;return true;}return false;} template<typename T> T gcd(T a, T b) { while(b) { a %= b; swap(a,b); } return a; } template<typename T> T lcm(T a, T b) { return a/gcd(a,b)*b; } /* ---------------------------------------------------------------- END OF TEMPLATE ---------------------------------------------------------------- Nguyen Ngoc Hung - nnhzzz Training for VOI24 gold medal ---------------------------------------------------------------- */ int a[MAXN],hi[MAXN][LOG],rgt[MAXN][LOG],ma[MAXN][LOG]; int n; #define combine(x,y) (a[(x)]<a[(y)]?(y):(x)) int get(int l, int r){ int k = log2(r-l+1); return combine(ma[l][k],ma[r-MASK(k)+1][k]); } bool F(int i, int l, int r){ return (i>=l && i<=r); } void init(int N, vi arr){ n = N; REP(i,1,n) a[i] = arr[i-1]; a[0] = a[n+1] = n+1; stack<int> st; st.push(0); REP(i,1,n){ while(a[st.top()]<a[i]) st.pop(); hi[i][0] = st.top(); st.push(i); } while(SZ(st)!=0) st.pop(); st.push(n+1); REPD(i,n,1){ while(a[st.top()]<a[i]) st.pop(); rgt[i][0] = st.top(); st.push(i); } rgt[0][0] = rgt[n+1][0] = n+1; REP(i,1,n){ ma[i][0] = i; hi[i][0] = combine(hi[i][0],rgt[i][0]); } REP(j,1,LOG-1){ REP(i,0,n+1){ hi[i][j] = hi[hi[i][j-1]][j-1]; rgt[i][j] = rgt[rgt[i][j-1]][j-1]; if(i+MASK(j)-1>n) continue; ma[i][j] = combine(ma[i][j-1],ma[i+MASK((j-1))][j-1]); } } } // 3 2 1 6 4 5 7 // 2-4 6-7 int minimum_jumps(int A, int B, int C, int D){ ++A; ++B; ++C; ++D; int CD = get(C,D),BC = get(B,C-1); if(a[BC]>a[CD]) return -1; int l = A,r = B,pos = A; while(l<=r){ int mid = (l+r)>>1; if(a[get(mid,B)]<a[CD]){ pos = mid; r = mid-1; }else{ l = mid+1; } } pos = get(pos,B); if(F(rgt[pos][0],C,D)) return 1; int res = 0; REPD(i,LOG-1,0){ int newpos = hi[pos][i]; if(rgt[newpos][0]<C){ pos = newpos; res += MASK(i); } } int newpos = hi[pos][0]; if(rgt[0][newpos]<=D){ pos = newpos; ++res; if(F(pos,C,D)) return res+1; } REPD(i,LOG-1,0){ newpos = rgt[pos][i]; if(newpos<C){ pos = newpos; res += MASK(i); } } return res+1; }

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

jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:101:5: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
  101 |     while(SZ(st)!=0) st.pop(); st.push(n+1);
      |     ^~~~~
jumps.cpp:101:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
  101 |     while(SZ(st)!=0) st.pop(); st.push(n+1);
      |                                ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...