이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, m, q, k, x, y, a, b, c;
vector<int> s, p, w, l;
bool testcase3, testcase2;
vector<ll> up[30];
vector<ll> upmx[30];
vector<ll> upm[30];
vector<ll> wins;
void init(int N, vector<int> S, vector<int> P, vector<int> W, vector<int> L) {
n = N;
s = S;
p = P;
w = W;
l = L;
testcase2 = 1;
set<ll> st;
for (int i = 0; i < n; i++) {
if (s[i] != p[i]) {
testcase2 = 0;
}
st.insert(s[i]);
}
if (testcase2) {
for (int i = 0; i < 30; i++) {
up[i].resize(n + 1);
upmx[i].resize(n + 1);
upm[i].resize(n + 1);
if (i == 0) {
for (int j = 0; j < n; j++) {
upm[i][j] = w[j];
up[i][j] = s[j];
upmx[i][j] = s[j] * 2 - up[i][j];
}
upm[i][n] = n;
upmx[i][n] = 0;
up[i][n] = 0;
}
else {
for (int j = 0; j < n + 1; j++) {
upm[i][j] = upm[i - 1][upm[i - 1][j]];
up[i][j] = up[i - 1][j] + up[i - 1][upm[i - 1][j]];
upmx[i][j] = max(upmx[i - 1][j], upmx[i - 1][upm[i - 1][j]] - up[i - 1][j]);
}
}
}
}
else if (st.size() == 1) {
testcase3 = 1;
for (int i = 0; i < 30; i++) {
up[i].resize(n + 1);
upm[i].resize(n + 1);
if (i == 0) {
for (int j = 0; j < n; j++) {
upm[i][j] = l[j];
up[i][j] = p[j];
}
upm[i][n] = n;
up[i][n] = 0;
}
else {
for (int j = 0; j < n + 1; j++) {
upm[i][j] = upm[i - 1][upm[i - 1][j]];
up[i][j] = up[i - 1][j] + up[i - 1][upm[i - 1][j]];
}
}
}
// cout << "DEBUG" << endl;
wins.resize(n + 1);
for (int i = n - 1; i >= 0; i--) {
// cout << i << ' ' << s[i] << endl;
wins[i] = s[i] + wins[w[i]];
}
}
}
long long simulate2(int x, ll z);
long long simulate3(int x, ll z);
long long simulate(int x, int z) {
if (testcase2) {
return simulate2(x, z);
}
if (testcase3) {
return simulate3(x, z);
}
while (x < n) {
if (z >= s[x]) {
z += s[x];
x = w[x];
}
else {
z += p[x];
x = l[x];
}
// cout << x << ' ' << z << '\n';
}
return z;
}
long long simulate2(int x, ll z) {
while (x < n) {
for (int i = 29; i >= 0; i--) {
// cout << i << ' ' << up[i][x] << '\n';
if (upmx[i][x] <= z) {
z += up[i][x];
x = upm[i][x];
}
}
if (x != n) {
z += p[x];
x = l[x];
}
}
return z;
}
long long simulate3(int x, ll z) {
for (int i = 29; i >= 0; i--) {
// cout << i << ' ' << up[i][x] << '\n';
if (z + up[i][x] < s[0] && upm[i][x] != n) {
// cout << z + up[i][x] << '\n';
z += up[i][x];
x = upm[i][x];
// cout << x << ' ' << z << '\n';
}
}
if (z < s[0]) {
z += p[x];
x = l[x];
}
// cout << x << ' ' << z << '\n';
z += wins[x];
// cout << n << ' ' << z << '\n';
return z;
}
# | 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... |