제출 #1008901

#제출 시각아이디문제언어결과실행 시간메모리
1008901Cookie밀림 점프 (APIO21_jumps)C++14
81 / 100
4088 ms73160 KiB
#include<bits/stdc++.h> #include<fstream> //#pragma GCC optimize("O3") //#pragma GCC target("avx2") using namespace std; #define sz(a) (int)a.size() #define ALL(v) v.begin(), v.end() #define ALLR(v) v.rbegin(), v.rend() #define ll long long #define pb push_back #define forr(i, a, b) for(int i = a; i < b; i++) #define dorr(i, a, b) for(int i = a; i >= b; i--) #define ld long double #define vt vector #include<fstream> #define fi first #define se second #define pll pair<ll, ll> #define pii pair<int, int> #define mpp make_pair const ld PI = 3.14159265359, prec = 1e-9;; //using u128 = __uint128_t; const int dx[4] = {1, 0, -1, 0}; const int dy[4] = {0, -1, 0, 1}; const ll mod = 1e9 + 7, pr = 31; const int mxn = 2e5 + 5, mxd = 250 * 250, sq = 100, mxv = 5e4 + 1, mxq = 2e6 + 5, T = 1000; //const int base = (1 <<18); const ll inf = 2e9 + 5, neg = -69420, inf2 = 1e14; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); #include <vector> #include <cassert> #include <cstdio> //#include "jumps.h" #include <vector> int n; bool sub1 = 1; int h[mxn + 1], l[mxn + 1], r[mxn + 1], dis[mxn + 1], up[mxn + 1][18], upr[mxn + 1][18]; pii mx[mxn + 1][18]; vt<int>adj[mxn + 1]; int getmx(int l, int r){ if(l > r)return(-1); int lg = __lg(r - l + 1); return(max(mx[l][lg], mx[r - (1 << lg) + 1][lg]).se); } void init(int N, std::vector<int> H) { n = N; for(int i = 1; i <= n; i++){ h[i] = H[i - 1]; sub1 &= (h[i] == i); } h[0] = inf; vt<int>st; for(int i = 1; i <= n; i++){ while(sz(st) && h[st.back()] <= h[i])st.pop_back(); if(sz(st))l[i] = st.back(); st.pb(i); } st.clear(); for(int i = n; i >= 1; i--){ while(sz(st) && h[st.back()] <= h[i])st.pop_back(); if(sz(st))r[i] = st.back(); st.pb(i); upr[i][0] = r[i]; } for(int i = 1; i <= n; i++){ if(h[l[i]] > h[r[i]])up[i][0] = l[i]; else up[i][0] = r[i]; mx[i][0] = mpp(h[up[i][0]], i); } for(int i = 1; i < 18; i++){ for(int j = 1; j <= n; j++){ up[j][i] = up[up[j][i - 1]][i - 1]; upr[j][i] = upr[upr[j][i - 1]][i - 1]; } for(int j = 1; j + (1 << i) - 1 <= n; j++){ mx[j][i] = max(mx[j][i - 1], mx[j + (1 << (i - 1))][i - 1]); } } for(int i = 1; i <= n; i++){ if(l[i])adj[i].pb(l[i]); if(r[i])adj[i].pb(r[i]); } } int minimum_jumps(int A, int B, int C, int D) { A++; B++; C++; D++; if(sub1)return(C - B); if(C == D){ int mx = -1, u = getmx(max(l[C] + 1, A), B); if(u == -1)return(-1); int ans = 0; for(int i = 17; i >= 0; i--){ if(h[up[u][i]] <= h[C]){ ans += (1 << i); u = up[u][i]; } } for(int i = 17; i >= 0; i--){ if(h[upr[u][i]] <= h[C]){ ans += (1 << i); u = upr[u][i]; } } if(u != C)return(-1); return(ans); }else{ queue<int>q; for(int i = 1; i <= n; i++)dis[i] = -1; for(int i = A; i <= B; i++){ dis[i] = 0; q.push(i); } while(!q.empty()){ int nw = q.front(); q.pop(); if(nw >= C && nw <= D)return(dis[nw]); for(auto i: adj[nw]){ if(dis[i] == -1){ dis[i] = dis[nw] + 1; q.push(i); } } } return -1; } } #include <vector> /* 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) 메시지

jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:91:13: warning: unused variable 'mx' [-Wunused-variable]
   91 |         int mx = -1, u = getmx(max(l[C] + 1, A), 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...