Submission #1261611

#TimeUsernameProblemLanguageResultExecution timeMemory
1261611alexddObstacles for a Llama (IOI25_obstacles)C++20
0 / 100
2096 ms8632 KiB
#include "obstacles.h" #include <bits/stdc++.h> using namespace std; vector<int> t,h; int maxl[200005]; int maxpref[200005]; void initialize(std::vector<int> T, std::vector<int> H) { t = T; h = H; maxpref[0] = t[0]; for(int i=1;i<t.size();i++) maxpref[i] = max(maxpref[i-1], t[i]); priority_queue<pair<int,int>> pq; for(int i=0;i<h.size();i++) { maxl[i] = 0; while(maxl[i] + 1 < t.size() && t[maxl[i]+1] > h[i]) maxl[i]++; maxl[i] = maxpref[maxl[i]]; pq.push({maxl[i], i}); } while(!pq.empty()) { auto [cval,i] = pq.top(); pq.pop(); if(maxl[i] != cval) continue; for(int v:{i-1,i+1}) { if(0 <= v && v < h.size() && maxl[v] < maxl[i] && h[v] < maxl[i]) { maxl[v] = maxl[i]; pq.push({maxl[v], v}); } } } } bool can_reach(int L, int R, int S, int D) { int maxh = 0; for(int i=L;i<=R;i++) maxh = max(maxh, h[i]); return (maxl[L] >= maxh && maxl[R] >= maxh); }
#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...