#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
const int N = 4e5+1;
const int lg = 28;
const int lgb = 11;
const int base = 5;
const long long inf = 2e9;
int up[lg][N][lgb];
int min_diff[lg][N][lgb];
long long sum[lg][N][lgb];
int n;
vector<int> s, p, w, l;
void init(int nn, std::vector<int> ss, std::vector<int> pp,
std::vector<int> ww, std::vector<int> ll) {
s=ss, p = pp, w = ww, l = ll;
n = nn;
auto start = clock();
for(int _ = 0;_<lg;_++) {
for(int i = 0;i<=n;i++) {
if(i == n) {
up[_][i][0] = n;
min_diff[_][i][0] = inf;
sum[_][i][0] = 0;
}
else if(s[i] < (1ll<<_)) {
up[_][i][0] = w[i];
min_diff[_][i][0] = inf;
sum[_][i][0] = s[i];
}
else {
up[_][i][0] = l[i];
min_diff[_][i][0] = s[i];
sum[_][i][0] = p[i];
}
}
for(int l = 1;l<lgb;l++) {
for(int i = 0;i<=n;i++) {
int at = i;
long long sm = 0;
long long mn_diff = inf;
for(int k = 0;k<base;k++) {
if(min_diff[_][at][l-1] != inf)
mn_diff = max(0ll, min(mn_diff, min_diff[_][at][l-1]-sm));
sm+=sum[_][at][l-1];
at=up[_][at][l-1];
}
up[_][i][l] = at;
min_diff[_][i][l] = mn_diff;
sum[_][i][l] = sm;
}
}
}
assert((clock()-start)/CLOCKS_PER_SEC < 4.0);
return;
}
long long simulate(int x, int zz) {
long long z = zz;
int cnt=0;
int idx=0;
while(1) {
if(x == n)break;
cnt++;
while((1ll<<idx) <= zz) {
idx++;
}
int ll = min(lg-1, idx);
for(int j = lgb-1;j>=0;j--) {
for(int _ = 1;_<base;_++) {
if(up[ll][x][j] == n or (ll < lg-1 and min_diff[ll][x][j] <= z))continue;
z += sum[ll][x][j];
x = up[ll][x][j];
}
}
if(s[x] <= z) {
z+=s[x];
x=w[x];
}
else if(s[x] > z) {
z+=p[x];
x=l[x];
}
}
return z;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
25436 KB |
Output is correct |
| 2 |
Correct |
2 ms |
25436 KB |
Output is correct |
| 3 |
Incorrect |
9 ms |
34072 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
29788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
29788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
29788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
29788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
29788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
