#include "dungeons.h"
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::vector;
using std::string;
using std::endl;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;
#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define ln "\n"
#define all(a) a.begin(), a.end()
#define pb emplace_back
#define mp std::make_pair
constexpr ll inf = (1ll<<60);
struct segment_tree{
ll N;
vi node;
segment_tree(int n){
N = 1;
while(N <= n) N *= 2;
node.resize(2*N,-inf);
}
void update(ll idx, ll val){
idx += N;
node[idx] = val;
idx /= 2;
while(idx){
node[idx] = compare(node[idx*2], node[idx*2+1]);
idx /= 2;
}
}
ll min_right(ll val, ll a, ll now = 1, ll l = 0, ll r = -1){
if(r == -1) r = N;
if(r <= a) return r;
if(val >= node[now]) return r;
if(now >= N) return l;
ll mid = min_right(val, a, now*2, l, (l+r)/2);
if(mid == (l+r)/2) return min_right(val, a, now*2+1, (l+r)/2, r);
return mid;
}
ll compare(ll l, ll r){
return std::max(l,r);
}
};
vii t1_edge, t1_weight;
vi t1_dist, t1_par, t1_next;
ll N;
vi S,P,W,L;
vii min, sum, idx;
constexpr ll LOG = 30;
void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
N = n+1;
rep(i,0,n) S.pb(s[i]), P.pb(p[i]), W.pb(w[i]), L.pb(l[i]);
{
t1_edge.resize(N);
t1_weight.resize(N);
t1_dist.resize(N);
t1_par.resize(N);
t1_next.resize(N);
rep(i,0,n){
t1_edge[w[i]].pb(i);
t1_weight[w[i]].pb(s[i]);
t1_par[i] = w[i];
}
vi dist2(N);
segment_tree seg(N+1);
vi v;
std::function<void(ll)> dfs = [&](ll now){
v.pb(now);
t1_next[now] = v[std::max(0ll, N-seg.min_right(s[now]+t1_dist[now], 0))];
seg.update(N-dist2[now], s[now]+t1_dist[now]);
for(auto next: t1_edge[now]){
dist2[next] = dist2[now]+1;
t1_dist[next] = t1_dist[now]+s[next];
dfs(next);
}
seg.update(N-dist2[now], -inf);
v.pop_back();
};
dfs(N-1);
}
{
min.resize(N,vi(LOG,-inf));
sum.resize(N,vi(LOG));
idx.resize(N,vi(LOG));
L.pb(N-1);
P.pb(0);
S.pb(-inf);
rep(i,0,N){
idx[i][0] = L[i];
sum[i][0] = P[i];
min[i][0] = S[i];
}
rep(j,1,LOG){
rep(i,0,N){
ll now = idx[i][j-1];
ll next = idx[now][j-1];
idx[i][j] = next;
sum[i][j] = sum[i][j-1]+sum[now][j-1];
min[i][j] = std::min(min[i][j-1], min[now][j-1]-sum[i][j-1]);
}
}
}
}
long long simulate(int x, int z) {
ll now = x;
ll ans = z;
while(true){
if(now == N-1) break;
if(S[now] > ans){
per(i,LOG-1,0){
if(min[now][i] > ans){
ans += sum[now][i];
now = idx[now][i];
}
}
}
else{
ans += t1_dist[now]-t1_dist[t1_next[now]];
now = t1_next[now];
}
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
3 ms |
2260 KB |
Output is correct |
4 |
Correct |
104 ms |
51076 KB |
Output is correct |
5 |
Correct |
3 ms |
2260 KB |
Output is correct |
6 |
Correct |
113 ms |
50816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1256 KB |
Output is correct |
2 |
Correct |
850 ms |
432536 KB |
Output is correct |
3 |
Correct |
814 ms |
453600 KB |
Output is correct |
4 |
Correct |
790 ms |
453460 KB |
Output is correct |
5 |
Correct |
992 ms |
400104 KB |
Output is correct |
6 |
Correct |
873 ms |
432920 KB |
Output is correct |
7 |
Correct |
752 ms |
453388 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1236 KB |
Output is correct |
2 |
Correct |
116 ms |
52388 KB |
Output is correct |
3 |
Correct |
115 ms |
56608 KB |
Output is correct |
4 |
Correct |
103 ms |
58604 KB |
Output is correct |
5 |
Correct |
116 ms |
55880 KB |
Output is correct |
6 |
Correct |
123 ms |
52084 KB |
Output is correct |
7 |
Correct |
127 ms |
52072 KB |
Output is correct |
8 |
Correct |
103 ms |
58368 KB |
Output is correct |
9 |
Correct |
108 ms |
51772 KB |
Output is correct |
10 |
Correct |
106 ms |
58264 KB |
Output is correct |
11 |
Correct |
154 ms |
52156 KB |
Output is correct |
12 |
Correct |
251 ms |
52244 KB |
Output is correct |
13 |
Correct |
222 ms |
51016 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1236 KB |
Output is correct |
2 |
Correct |
116 ms |
52388 KB |
Output is correct |
3 |
Correct |
115 ms |
56608 KB |
Output is correct |
4 |
Correct |
103 ms |
58604 KB |
Output is correct |
5 |
Correct |
116 ms |
55880 KB |
Output is correct |
6 |
Correct |
123 ms |
52084 KB |
Output is correct |
7 |
Correct |
127 ms |
52072 KB |
Output is correct |
8 |
Correct |
103 ms |
58368 KB |
Output is correct |
9 |
Correct |
108 ms |
51772 KB |
Output is correct |
10 |
Correct |
106 ms |
58264 KB |
Output is correct |
11 |
Correct |
154 ms |
52156 KB |
Output is correct |
12 |
Correct |
251 ms |
52244 KB |
Output is correct |
13 |
Correct |
222 ms |
51016 KB |
Output is correct |
14 |
Correct |
2 ms |
1236 KB |
Output is correct |
15 |
Correct |
173 ms |
52216 KB |
Output is correct |
16 |
Correct |
118 ms |
52436 KB |
Output is correct |
17 |
Correct |
112 ms |
55104 KB |
Output is correct |
18 |
Correct |
112 ms |
54976 KB |
Output is correct |
19 |
Correct |
167 ms |
52088 KB |
Output is correct |
20 |
Correct |
120 ms |
55752 KB |
Output is correct |
21 |
Correct |
116 ms |
56004 KB |
Output is correct |
22 |
Execution timed out |
7067 ms |
53860 KB |
Time limit exceeded |
23 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1236 KB |
Output is correct |
2 |
Correct |
116 ms |
52388 KB |
Output is correct |
3 |
Correct |
115 ms |
56608 KB |
Output is correct |
4 |
Correct |
103 ms |
58604 KB |
Output is correct |
5 |
Correct |
116 ms |
55880 KB |
Output is correct |
6 |
Correct |
123 ms |
52084 KB |
Output is correct |
7 |
Correct |
127 ms |
52072 KB |
Output is correct |
8 |
Correct |
103 ms |
58368 KB |
Output is correct |
9 |
Correct |
108 ms |
51772 KB |
Output is correct |
10 |
Correct |
106 ms |
58264 KB |
Output is correct |
11 |
Correct |
154 ms |
52156 KB |
Output is correct |
12 |
Correct |
251 ms |
52244 KB |
Output is correct |
13 |
Correct |
222 ms |
51016 KB |
Output is correct |
14 |
Correct |
2 ms |
1236 KB |
Output is correct |
15 |
Correct |
173 ms |
52216 KB |
Output is correct |
16 |
Correct |
118 ms |
52436 KB |
Output is correct |
17 |
Correct |
112 ms |
55104 KB |
Output is correct |
18 |
Correct |
112 ms |
54976 KB |
Output is correct |
19 |
Correct |
167 ms |
52088 KB |
Output is correct |
20 |
Correct |
120 ms |
55752 KB |
Output is correct |
21 |
Correct |
116 ms |
56004 KB |
Output is correct |
22 |
Execution timed out |
7067 ms |
53860 KB |
Time limit exceeded |
23 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1256 KB |
Output is correct |
2 |
Correct |
850 ms |
432536 KB |
Output is correct |
3 |
Correct |
814 ms |
453600 KB |
Output is correct |
4 |
Correct |
790 ms |
453460 KB |
Output is correct |
5 |
Correct |
992 ms |
400104 KB |
Output is correct |
6 |
Correct |
873 ms |
432920 KB |
Output is correct |
7 |
Correct |
752 ms |
453388 KB |
Output is correct |
8 |
Correct |
2 ms |
1236 KB |
Output is correct |
9 |
Correct |
116 ms |
52388 KB |
Output is correct |
10 |
Correct |
115 ms |
56608 KB |
Output is correct |
11 |
Correct |
103 ms |
58604 KB |
Output is correct |
12 |
Correct |
116 ms |
55880 KB |
Output is correct |
13 |
Correct |
123 ms |
52084 KB |
Output is correct |
14 |
Correct |
127 ms |
52072 KB |
Output is correct |
15 |
Correct |
103 ms |
58368 KB |
Output is correct |
16 |
Correct |
108 ms |
51772 KB |
Output is correct |
17 |
Correct |
106 ms |
58264 KB |
Output is correct |
18 |
Correct |
154 ms |
52156 KB |
Output is correct |
19 |
Correct |
251 ms |
52244 KB |
Output is correct |
20 |
Correct |
222 ms |
51016 KB |
Output is correct |
21 |
Correct |
2 ms |
1236 KB |
Output is correct |
22 |
Correct |
173 ms |
52216 KB |
Output is correct |
23 |
Correct |
118 ms |
52436 KB |
Output is correct |
24 |
Correct |
112 ms |
55104 KB |
Output is correct |
25 |
Correct |
112 ms |
54976 KB |
Output is correct |
26 |
Correct |
167 ms |
52088 KB |
Output is correct |
27 |
Correct |
120 ms |
55752 KB |
Output is correct |
28 |
Correct |
116 ms |
56004 KB |
Output is correct |
29 |
Execution timed out |
7067 ms |
53860 KB |
Time limit exceeded |
30 |
Halted |
0 ms |
0 KB |
- |