제출 #1008896

#제출 시각아이디문제언어결과실행 시간메모리
1008896Cookie밀림 점프 (APIO21_jumps)C++14
37 / 100
4078 ms16836 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]; vt<int>adj[mxn + 1]; 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); } 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); } 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); 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; } */
#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...