This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "dungeons.h"
#include <bits/stdc++.h>
#define pb push_back
#define x first
#define y second
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()
#define rd() abs((int)rng())
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
const int maxn = 2e5 + 10;
const int mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int LOG = 25;
vector<vector<vector<ll> > >sum(400001, vector<vector<ll> >(LOG));
vector<vector<vector<ll> > >mn(400001, vector<vector<ll> >(LOG));
vector<vector<vector<int> > >jump(400001, vector<vector<int> >(LOG));
int n;
vector<int>s, p, w, l;
void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L) {
n = N;
s = S, p = P, w = W, l = L;
s.pb(0);
p.pb(0);
w.pb(0);
l.pb(0);
for (int i = 0; i <= n; i++) {
for (int grp = 0; grp < LOG; grp++) {
sum[i][grp] = vector<ll>(grp + 1, 0);
mn[i][grp] = vector<ll>(grp + 1, 1e18);
jump[i][grp] = vector<int>(grp + 1, -1);
}
}
w[n] = n;
for (int grp = 0; grp < LOG; grp++) {
int upto = 1 << grp;
vector<int>nodes;
vector<int>in_grp(n + 1);
for (int i = 0; i < n; i++) {
if (s[i] <= upto || p[i] <= upto) {
nodes.pb(i);
in_grp[i] = 1;
}
}
for (int jmp = 0; jmp < grp; jmp++) {
for (int i : nodes) {
if (jmp == 0) {
int to;
if (s[i] <= upto) {
sum[i][grp][0] = s[i];
to = w[i];
} else {
sum[i][grp][0] = p[i];
mn[i][grp][0] = s[i];
to = l[i];
}
jump[i][grp][0] = to;
} else {
int x = jump[i][grp][jmp - 1];
if (x != -1 && in_grp[x]) {
sum[i][grp][jmp] = sum[i][grp][jmp - 1] + sum[x][grp][jmp - 1];
mn[i][grp][jmp] = min(mn[i][grp][jmp - 1], mn[x][grp][jmp - 1] - sum[i][grp][jmp - 1]);
jump[i][grp][jmp] = jump[x][grp][jmp - 1];
} else {
jump[i][grp][jmp] = -1;
}
}
}
}
}
}
ll simulate(int x, int z) {
ll cur_sum = z;
int cur = x;
for (int grp = 0; grp < LOG - 1; grp++) {
ll group_lower_bound = 1 << grp;
if (cur_sum >= group_lower_bound * 2) {
continue;
}
// if (cur_sum < group_lower_bound) {
// exit(3);
// }
for (int jmp = grp; jmp >= 0; jmp--) {
if (jump[cur][grp][jmp] == -1
|| (cur_sum + sum[cur][grp][jmp] >= group_lower_bound * 2)
|| (cur_sum >= mn[cur][grp][jmp])) {
continue;
}
cur_sum += sum[cur][grp][jmp];
cur = jump[cur][grp][jmp];
}
// cout << cur << " " << cur_sum << " " << jump[cur][grp][0] << " " << sum[cur][grp][0] << " " << mn[cur][grp][0] << "\n";
if (cur_sum >= s[cur]) {
cur_sum += s[cur];
cur = w[cur];
} else {
cur_sum += p[cur];
cur = l[cur];
}
// if (grp != LOG - 1 && cur != n && cur_sum < group_lower_bound * 2) {
// exit(3);
// }
// cout << "after finishing group " << grp << " we are at " << cur << " with strength " << cur_sum << "\n";
if (cur == n) {
return cur_sum;
}
}
for (int jmp = LOG - 1; jmp >= 0; jmp--) {
if (jump[cur][LOG - 1][jmp] != -1 && jump[cur][LOG - 1][jmp] != n) {
cur_sum += sum[cur][LOG - 1][jmp];
cur = jump[cur][LOG - 1][jmp];
}
}
if (cur_sum >= s[cur]) {
cur_sum += s[cur];
cur = w[cur];
} else {
cur_sum += p[cur];
cur = l[cur];
}
return cur_sum;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |