제출 #1236307

#제출 시각아이디문제언어결과실행 시간메모리
1236307AMel0nRainforest Jumps (APIO21_jumps)C++20
0 / 100
4037 ms13384 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define FOR(i,N) for(ll i = 0; i < N; i++) #define all(x) (x).begin(), (x).end() #define F first #define S second #include "jumps.h" int N; vector<int> H; vector<vector<int>> g; void init(int N, std::vector<int> H) { ::N = N; ::H = H; g.resize(N); FOR(x, N) { for(int y = x-1; y >= 0; y--) { if (H[y] > H[x]) { g[x].push_back(y); break; } } for(int y = x+1; y < N; y++) { if (H[y] > H[x]) { g[x].push_back(y); break; } } } // Subtask 4: binary search + segtree query(0, m) & query(m, N-1) // FOR(i, N) { // int l = 0, r = i; // while(l < r) {} // } } int minimum_jumps(int A, int B, int C, int D) { pair<int,int> res = {1e9,-1}; priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>> > pq; for(int i = A; i <= B; i++) pq.push({0, i}); vector<int> vis(N, 1e9); while(pq.size()) { int d = pq.top().F; int u = pq.top().S; pq.pop(); if (vis[u] < d) continue; vis[u] = d; if (C <= u && u <= D) { if (res.F > d) { res = {d, 1}; } else if (res.F == d) { res.S++; } continue; } for(int v: g[u]) { pq.push({d+1, v}); } } return res.S; }
#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...