제출 #958343

#제출 시각아이디문제언어결과실행 시간메모리
958343Itamar밀림 점프 (APIO21_jumps)C++14
27 / 100
1036 ms59904 KiB
#include "jumps.h" using namespace std; #include <vector> #include <stack> #include <algorithm> #define vi vector<int> const int siz = 2e5 + 2; #define pi pair<int,int> #define x first #define y second int h[siz]; struct node { int l, r, mid; pi maxi ={0,0}; node* sl=NULL, * sr=NULL; node(int li, int ri) { l = li, r = ri, mid = (l + r) / 2; } void ini() { if (l < r) { sl = new node(l, mid); sr = new node(mid + 1, r); sl->ini(); sr->ini(); maxi = max(sl->maxi, sr->maxi); } else maxi = { h[l],l }; } pi query(int a, int b) { if (a > b)return { 0,0 }; if (a > r || b < l) return { 0,a }; if (a <= l && b >= r)return maxi; return max(sl->query(a,b), sr->query(a,b)); } }; node* seg[siz]; int bin[siz][20][2]; int l[siz], r[siz]; int n; int ll[siz], rr[siz]; void init(int N, std::vector<int> H) { seg[0] = new node(0, N); n = N; vi his(N + 1); for (int i = 0; i < N; i++)h[i] = H[i]; seg[0]->ini(); stack<pi> s; s.push({ 1e9,-1 }); for (int i = 0; i < N; i++) {bin[i][0][0] = -1, bin[i][0][1] = -1;} for (int i = 0; i < N; i++) { while (s.top().x < h[i]) { s.pop(); } l[i] = s.top().y; ll[i] = s.top().x; s.push({ h[i],i }); } while (s.size() > 1)s.pop(); for (int i = N - 1; i >= 0; i--) { while (s.top().x < h[i]) { s.pop(); } r[i] = s.top().y; rr[i] = s.top().x; s.push({ h[i],i }); } for (int i = 0; i < N; i++) { if (rr[i] == 1e9)rr[i] = -1; if (ll[i] == 1e9)ll[i] = -1; if (rr[i] < ll[i]) { swap(ll[i], rr[i]); swap(l[i], r[i]); } bin[i][0][1] = r[i]; if (l[i] == -1)bin[i][0][0] = r[i]; else bin[i][0][0] = l[i]; } for (int j = 1; j < 20; j++) { for (int i = 0; i < N; i++) { for (int k = 0; k < 2; k++) { if (bin[i][j - 1][k] >= 0)bin[i][j][k] = bin[bin[i][j - 1][k]][j - 1][k]; else bin[i][j][k] = -1; } } } } int minimum_jumps(int A, int B, int C, int D) { int ans = 0; int m, mid; pi ps; m = seg[0]->query(C, D).x; int ss = A, e = B; /*while (ss < e) { int midmid = (ss + e) / 2; pi p = seg[0]->query(midmid, B); if (p.x > m) { ss = midmid + 1; } else e = midmid; }*/ ps = seg[0]->query(ss, B); mid = seg[0]->query(B + 1, C - 1).x; int s = ps.y; if (ps.x>m)return -1; if (C == B + 1)return 1; if (mid > m)return -1; if (mid < ps.x)return 1; for (int d = 19; d >= 0; d--) { int st = bin[s][d][1]; if (st != -1) { if (h[st] < mid) { s = st; ans += (1 << d); } } } if (h[bin[s][0][1]] < m)return ans + 2; for (int d = 19; d >= 0; d--) { int st = bin[s][d][0]; if (st != -1) { if (h[st] < mid) { s = st; ans += (1 << d); } } } return ans + 2; }

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

jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:68:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   68 |   if (rr[i] == 1e9)rr[i] = -1; if (ll[i] == 1e9)ll[i] = -1;
      |   ^~
jumps.cpp:68:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   68 |   if (rr[i] == 1e9)rr[i] = -1; if (ll[i] == 1e9)ll[i] = -1;
      |                                ^~
jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:89:15: warning: unused variable 'e' [-Wunused-variable]
   89 |   int ss = A, e = B;
      |               ^
#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...