이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, ll>
const ll oo = 1e9 + 9;
const int MAX = 50005;
const int LOGMAX = 27;
const int startLog = 10;
int n;
vector<int> S, W, P, L;
struct G{
array<ll, 3> par[LOGMAX + 1][MAX];
void preCalc(){
for (int j = 1; j <= LOGMAX; j++)
{
for (int i = 0; i <= n; i++)
{
int m = par[j - 1][i][0];
par[j][i][0] = par[j - 1][m][0];
par[j][i][1] = par[j - 1][i][1] + par[j - 1][m][1];
par[j][i][2] = max(par[j - 1][i][2], par[j - 1][m][2] + par[j - 1][i][1]);
}
}
}
pii lift(ll start, ll target, int v){
if(start >= target || v == n) return {v, start};
for(int j = LOGMAX; j >= 0 && v != n && start < target; --j){
if(start + par[j][v][2] < 0){
start = start + par[j][v][1];
v = par[j][v][0];
}
}
if(v == n){
return {n, start};
}
if(start >= S[v]){
start += S[v];
v = W[v];
}
else{
start += P[v];
v = L[v];
}
return {v, start};
}
};
vector<ll> v;
G gs[LOGMAX - startLog + 1];
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;
for(int i = startLog; i < LOGMAX; ++i){
v.push_back((1 << i));
}
for (int i = 0; i < v.size(); i++)
{
for(int j = 0; j <= N; ++j){
if(j == N){
gs[i].par[0][j] = {N, 0, -oo * oo};
continue;
}
if(s[j] > v[i]){
gs[i].par[0][j] = {l[j], p[j], p[j] - s[j]};
}
else{
gs[i].par[0][j] = {w[j], s[j], -oo * oo};
}
}
gs[i].preCalc();
}
v.push_back(oo * oo);
return;
}
ll simulate(int x, int z) {
ll u = x;
ll s = z;
while(s < (1 << startLog) && u != n){
if(s >= S[u]){
s += S[u];
u = W[u];
}
else{
s += P[u];
u = L[u];
}
}
for (int i = 0; i < v.size() - 1; i++)
{
while(u != n && s < v[i + 1]){
pii p = gs[i].lift(s, v[i + 1], u);
u = p.first;
s = p.second;
}
}
return s;
}
컴파일 시 표준 에러 (stderr) 메시지
dungeons.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:68:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for (int i = 0; i < v.size(); i++)
| ~~^~~~~~~~~~
dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:101:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | for (int i = 0; i < v.size() - 1; i++)
| ~~^~~~~~~~~~~~~~
# | 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... |