제출 #864811

#제출 시각아이디문제언어결과실행 시간메모리
864811hgmhc밀림 점프 (APIO21_jumps)C++17
0 / 100
808 ms62908 KiB
#include <bits/stdc++.h> using namespace std; using ii = pair<int, int>; using ll = long long; using vi = vector<int>; #define rep(i, a, b) for (auto i = (a); i <= (b); ++i) #define per(i, a, b) for (auto i = (b); i >= (a); --i) #define all(x) begin(x), end(x) #define siz(x) int((x).size()) #define Mup(x, y) x = max(x, y) #define mup(x, y) x = min(x, y) #define fi first #define se second #define dbg(...) fprintf(stderr, __VA_ARGS__) #define ensure(...) if (!(__VA_ARGS__)) { fprintf(stderr, "Error in %dth line.", __LINE__), exit(-1); } template <const int N> struct segtree { int t[2*N]{}; int &operator [] (int i){ return t[N+i]; } void build() { per(i,1,N-1) t[i] = max(t[2*i],t[2*i+1]); } int query(int a, int b) { int res = 0; for (a += N, b += N; a <= b; ++a /= 2, --b /= 2) { if (a&1) Mup(res,t[a]); if (~b&1) Mup(res,t[b]); } return res; } }; const int N = 2e5; vi adj[N]; int mj[N][20], lj[N][20], rj[N][20], Arg[N+1]; segtree<N> ds; void construct_graph(int n, vi &H) { stack<int> S; rep(i,0,n-1) { while (not S.empty() and H[S.top()] < H[i]) S.pop(); if (not S.empty()) adj[i].push_back(S.top()); S.push(i); } while (not S.empty()) S.pop(); per(i,0,n-1) { while (not S.empty() and H[S.top()] < H[i]) S.pop(); if (not S.empty()) adj[i].push_back(S.top()); S.push(i); } } void construct_sparsetable(int n, vi &H) { rep(i,0,n-1) { ensure(not adj[i].empty() or H[i] == n); if (adj[i].empty()) { mj[i][0] = lj[i][0] = rj[i][0] = i; } else if (siz(adj[i]) == 1) { mj[i][0] = adj[i][0]; lj[i][0] = adj[i][0] < i ? adj[i][0] : i; rj[i][0] = adj[i][0] > i ? adj[i][0] : i; } else if (siz(adj[i]) == 2) { mj[i][0] = H[adj[i][0]] < H[adj[i][1]] ? adj[i][1] : adj[i][0]; lj[i][0] = adj[i][0], rj[i][0] = adj[i][1]; if (lj[i][0] > rj[i][0]) swap(lj[i][0],rj[i][0]); } else ensure(0); } rep(k,1,19) rep(i,0,n-1) { mj[i][k] = mj[mj[i][k-1]][k-1]; lj[i][k] = lj[lj[i][k-1]][k-1]; rj[i][k] = rj[rj[i][k-1]][k-1]; } } void init(int N, vi H) { construct_graph(N, H); construct_sparsetable(N, H); rep(i,0,N-1) ds[i] = H[i], Arg[H[i]] = i; ds.build(); } int A, B, C, D, hurdle; const int INF = 1e9; int dist(int x, int y) { if (ds.query(x,y-1) > ds[y]) return INF; int res = 0; if (x == y) return 0; per(i,0,19) while (ds[mj[x][i]] < ds[y]) x=mj[x][i], res += 1<<i; if (mj[x][0] == y) return res+1; per(i,0,19) while (x<rj[x][i] and ds[rj[x][i]] < ds[y]) x=rj[x][i], res += 1<<i; if (rj[x][0] == y) return res+1; ensure(0); } int tisd(int y, int x) { if (ds.query(y+1,x) > ds[y]) return INF; int res = 0; if (x == y) return 0; per(i,0,19) while (ds[mj[x][i]] < ds[y]) x=mj[x][i], res += 1<<i; if (mj[x][0] == y) return res+1; per(i,0,19) while (lj[x][i]<x and ds[lj[x][i]] < ds[y]) x=lj[x][i], res += 1<<i; if (lj[x][0] == y) return res+1; ensure(0); } int dist_lr(int a, int b, int y) { if (ds.query(b,y-1) > ds[y]) return INF; int res = 0, x = b; per(i,0,19) while (a<=lj[x][i]&&lj[x][i]<x and ds[lj[x][i]]<ds[y]) x=lj[x][i]; return dist(x,y); } int dist_rl(int y, int a, int b) { if (ds.query(y+1,a) > ds[y]) return INF; int res = 0, x=a; per(i,0,19) while (x<rj[x][i]&&rj[x][i]<=b and ds[rj[x][i]]<ds[y]) x=rj[x][i]; return tisd(y,x); } int ga() { return dist_lr(0,B,Arg[ds.query(B,C-1)])+1; } int na() { int x = B-1; per(i,0,19) while(A<=lj[x][i]&&lj[x][i]<x and ds[lj[x][i]]<hurdle) x=lj[x][i]; if (A<=lj[x][0] && ds[lj[x][0]]>=hurdle) { if (ds.query(lj[x][0],C-1) <= ds.query(C,D)) return 1; } return INF; } int da() { int x = A-1; per(i,0,19) while(lj[x][i]<x and ds[lj[x][i]]<hurdle) x=lj[x][i]; if (ds[lj[x][0]]>=hurdle) { return dist_rl(lj[x][0],A,B)+1; } return INF; } int minimum_jumps(int A, int B, int C, int D) { if (ds.query(B,C-1) > ds.query(C,D)) return -1; ::A = A, ::B = B, ::C = C, ::D = D; hurdle = ds.query(B,C-1); return min({ga(), na(), da()}); } #ifdef LOCAL int main() { int N, Q; ensure(2 == scanf("%d %d", &N, &Q)); std::vector<int> H(N); for (int i = 0; i < N; ++i) { ensure(1 == scanf("%d", &H[i])); } init(N, H); for (int i = 0; i < Q; ++i) { int A, B, C, D; ensure(4 == scanf("%d %d %d %d", &A, &B, &C, &D)); printf("%d\n", minimum_jumps(A, B, C, D)); } return 0; } #endif

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

jumps.cpp: In function 'int dist_lr(int, int, int)':
jumps.cpp:115:9: warning: unused variable 'res' [-Wunused-variable]
  115 |     int res = 0, x = b;
      |         ^~~
jumps.cpp: In function 'int dist_rl(int, int, int)':
jumps.cpp:122:9: warning: unused variable 'res' [-Wunused-variable]
  122 |     int res = 0, x=a;
      |         ^~~
#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...