제출 #439210

#제출 시각아이디문제언어결과실행 시간메모리
439210Sorting던전 (IOI21_dungeons)C++17
37 / 100
7026 ms192560 KiB
#include "dungeons.h" #include <vector> #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 4e5 + 3; const int C = 10000; const int LOGN = 19; const ll INF = 1e18; int n; vector<int> s, p, w, l; array<ll, 3> up[LOGN][N]; // pos, strength, max void init(int _n, vector<int> _s, vector<int> _p, vector<int> _w, vector<int> _l) { n = _n, swap(s, _s), swap(p, _p), swap(w, _w), swap(l, _l); for(int i = 0; i < n; ++i){ if(s[i] <= C) up[0][i] = {i, 0, -INF}; else up[0][i] = {i, 0, -s[i]}; } for(int j = 1; j < LOGN; ++j){ for(int i = 0; i < n; ++i){ if(up[j - 1][i][0] == n){ up[j][i] = {n, -1, -1}; continue; } int a = up[j - 1][i][0], b; ll add; if(s[a] <= C){ b = w[a]; add = s[a]; } else{ b = l[a]; add = p[a]; } if(b == n || up[j - 1][b][0] == n){ up[j][i] = {n, -1, -1}; continue; } up[j][i][0] = up[j - 1][b][0]; up[j][i][1] = up[j - 1][i][1] + add + up[j - 1][b][1]; up[j][i][2] = max(up[j - 1][i][2], up[j - 1][i][1] + add + up[j - 1][b][2]); } } } long long simulate(int x, int z) { ll ans = z; while(ans < C && x != n){ if(ans >= s[x]){ ans += s[x]; x = w[x]; } else{ ans += p[x]; x = l[x]; } } while(x != n){ for(int j = LOGN - 1; j >= 0; --j){ if(up[j][x][0] == n) continue; if(up[j][x][2] + ans < 0){ ans += up[j][x][1]; x = up[j][x][0]; } } if(s[x] <= ans){ ans += s[x]; x = w[x]; } else{ ans += p[x]; x = l[x]; } } return ans; }
#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...