# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
761193 |
2023-06-19T10:52:00 Z |
ksu2009en |
Peru (RMI20_peru) |
C++17 |
|
248 ms |
123376 KB |
#include "peru.h"
#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <cmath>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <bitset>
#include <cstring>
#include <unordered_map>
using namespace std;
typedef long long ll;
ll const mod = (ll)(1e9 + 7);
struct one{
ll res, min_dp, mx, mod;
};
one t[4 * 400000 + 7];
void build(ll v, ll l, ll r){
if(l == r){
t[v].res = t[v].min_dp = t[v].mx = (ll)(2500000) * (ll)(2000000000) + 1;
t[v].mod = -1;
return;
}
ll mid = (l + r) >> 1;
build(2 * v, l, mid);
build(2 * v + 1, mid + 1, r);
t[v].res = t[v].min_dp = t[v].mx = (ll)(2500000) * (ll)(2000000000) + 1;
t[v].mod = -1;
}
void push(ll v, ll l, ll r){
if(l != r && t[v].mod != -1){
//cout << " pushing " << l << ' ' << r << ' ' << t[v].mod << endl;
t[2 * v].mod = max(t[2 * v].mod, t[v].mod);
t[2 * v].res = t[2 * v].min_dp + t[2 * v].mod;
//cout << " left son val :::::::: " << l << ' ' << r << ' ' << t[2 * v].res << endl;
t[2 * v + 1].mod = max(t[2 * v + 1].mod, t[v].mod);
t[2 * v + 1].res = t[2 * v + 1].min_dp + t[2 * v + 1].mod;
t[v].mod = -1;
}
}
void update_dp(ll v, ll l, ll r, ll pos, ll val, ll mx){
if(l == r){
t[v].min_dp = val;
t[v].res = val + mx;
t[v].mod = mx;
//cout << " update_dp " << l << ' ' << r << ' ' << t[v].res << ' ' << t[v].min_dp << endl;
return;
}
ll mid = (l + r) >> 1;
push(v, l, r);
if(pos <= mid)
update_dp(2 * v, l, mid, pos, val, mx);
else
update_dp(2 * v + 1, mid + 1, r, pos, val, mx);
t[v].res = min(t[2 * v].res, t[2 * v + 1].res);
//cout << l << ' ' << mid << ' ' << t[2 * v].res << endl;
//cout << " update_dp " << l << ' ' << r << ' ' << t[v].res << ' ' << pos << ' ' << val << ' ' << mx << endl;
t[v].min_dp = min(t[2 * v].min_dp, t[2 * v + 1].min_dp);
}
void update_mx(ll v, ll l, ll r, ll ql, ll qr, ll mx){
if(r < ql || qr < l)
return;
if(ql <= l && r <= qr){
t[v].mod = max(t[v].mod, mx);
t[v].res = t[v].min_dp + t[v].mod;
// cout << l << ' ' << r << ' ' << t[v].mod << endl;
return;
}
ll mid = (l + r) >> 1;
push(v, l, r);
update_mx(2 * v, l, mid, ql, qr, mx);
update_mx(2 * v + 1, mid + 1, r, ql, qr, mx);
t[v].res = min(t[2 * v].res, t[2 * v + 1].res);
t[v].min_dp = min(t[2 * v].min_dp, t[2 * v + 1].min_dp);
}
ll get_min(ll v, ll l, ll r, ll ql, ll qr){
if(r < ql || qr < l)
return (ll)(2500000) * (ll)(2000000000) + 1;
if(ql <= l && r <= qr){
// cout << "geting getting getting getiing getting " << l << ' ' << r << ' ' << t[v].res << endl;
return t[v].res;
}
ll mid = (l + r) >> 1;
push(v, l, r);
return min(get_min(2 * v, l, mid, ql, qr), get_min(2 * v + 1, mid + 1, r, ql, qr));
}
int solve(int n, int k, int* b){
vector<ll>dp(n + 1), a(n + 1);
for(int i = 0; i < n; i++)
a[i + 1] = b[i];
build(1, 1, n);
dp[1] = a[1];
update_dp(1, 1, n, 1, 0, a[1]);
for(int i = 2; i <= n; i++){
dp[i] = (dp[i - 1] + (ll)a[i]);
update_dp(1, 1, n, i, dp[i - 1], a[i]);
ll mx = 0;
ll last = 1;
for(int j = i - 1; j >= max(0, i - k + 1); j--){
mx = max(mx, (ll)a[j]);
if(mx > a[i]){
last = j + 1;
break;
}
}
// cout << "LAST " << last << endl;
if(last <= i - 1)
update_mx(1, 1, n, last, i - 1, a[i]);
// cout << get_min(1, 1, n, i - k + 1, i) << endl;
dp[i] = get_min(1, 1, n, i - k + 1, i);
}
ll p = 1;
ll ans = 0;
for(int i = n; i >= 1; i--){
dp[i] %= mod;
ans = (ans + (p * dp[i]) % mod) % mod;
p = (p * 23) % mod;
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
1 ms |
488 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
468 KB |
Output is correct |
9 |
Correct |
2 ms |
468 KB |
Output is correct |
10 |
Correct |
1 ms |
468 KB |
Output is correct |
11 |
Correct |
1 ms |
468 KB |
Output is correct |
12 |
Correct |
1 ms |
468 KB |
Output is correct |
13 |
Correct |
1 ms |
468 KB |
Output is correct |
14 |
Correct |
1 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
1 ms |
488 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
468 KB |
Output is correct |
9 |
Correct |
2 ms |
468 KB |
Output is correct |
10 |
Correct |
1 ms |
468 KB |
Output is correct |
11 |
Correct |
1 ms |
468 KB |
Output is correct |
12 |
Correct |
1 ms |
468 KB |
Output is correct |
13 |
Correct |
1 ms |
468 KB |
Output is correct |
14 |
Correct |
1 ms |
468 KB |
Output is correct |
15 |
Correct |
187 ms |
41044 KB |
Output is correct |
16 |
Correct |
198 ms |
41068 KB |
Output is correct |
17 |
Correct |
169 ms |
41044 KB |
Output is correct |
18 |
Correct |
248 ms |
41100 KB |
Output is correct |
19 |
Correct |
224 ms |
41104 KB |
Output is correct |
20 |
Correct |
218 ms |
41044 KB |
Output is correct |
21 |
Correct |
178 ms |
45280 KB |
Output is correct |
22 |
Correct |
173 ms |
45192 KB |
Output is correct |
23 |
Correct |
173 ms |
45196 KB |
Output is correct |
24 |
Correct |
185 ms |
45120 KB |
Output is correct |
25 |
Correct |
175 ms |
45196 KB |
Output is correct |
26 |
Correct |
167 ms |
45164 KB |
Output is correct |
27 |
Correct |
173 ms |
45196 KB |
Output is correct |
28 |
Correct |
177 ms |
45200 KB |
Output is correct |
29 |
Correct |
179 ms |
45200 KB |
Output is correct |
30 |
Correct |
178 ms |
45124 KB |
Output is correct |
31 |
Correct |
184 ms |
45200 KB |
Output is correct |
32 |
Correct |
175 ms |
45152 KB |
Output is correct |
33 |
Correct |
164 ms |
45136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
187 ms |
41044 KB |
Output is correct |
2 |
Correct |
198 ms |
41068 KB |
Output is correct |
3 |
Correct |
169 ms |
41044 KB |
Output is correct |
4 |
Correct |
248 ms |
41100 KB |
Output is correct |
5 |
Correct |
224 ms |
41104 KB |
Output is correct |
6 |
Correct |
218 ms |
41044 KB |
Output is correct |
7 |
Correct |
178 ms |
45280 KB |
Output is correct |
8 |
Correct |
173 ms |
45192 KB |
Output is correct |
9 |
Correct |
173 ms |
45196 KB |
Output is correct |
10 |
Correct |
185 ms |
45120 KB |
Output is correct |
11 |
Correct |
175 ms |
45196 KB |
Output is correct |
12 |
Correct |
167 ms |
45164 KB |
Output is correct |
13 |
Correct |
173 ms |
45196 KB |
Output is correct |
14 |
Correct |
177 ms |
45200 KB |
Output is correct |
15 |
Correct |
179 ms |
45200 KB |
Output is correct |
16 |
Correct |
178 ms |
45124 KB |
Output is correct |
17 |
Correct |
184 ms |
45200 KB |
Output is correct |
18 |
Correct |
175 ms |
45152 KB |
Output is correct |
19 |
Correct |
164 ms |
45136 KB |
Output is correct |
20 |
Correct |
1 ms |
468 KB |
Output is correct |
21 |
Correct |
1 ms |
468 KB |
Output is correct |
22 |
Correct |
1 ms |
468 KB |
Output is correct |
23 |
Correct |
1 ms |
468 KB |
Output is correct |
24 |
Correct |
1 ms |
488 KB |
Output is correct |
25 |
Correct |
1 ms |
468 KB |
Output is correct |
26 |
Correct |
1 ms |
468 KB |
Output is correct |
27 |
Correct |
1 ms |
468 KB |
Output is correct |
28 |
Correct |
2 ms |
468 KB |
Output is correct |
29 |
Correct |
1 ms |
468 KB |
Output is correct |
30 |
Correct |
1 ms |
468 KB |
Output is correct |
31 |
Correct |
1 ms |
468 KB |
Output is correct |
32 |
Correct |
1 ms |
468 KB |
Output is correct |
33 |
Correct |
1 ms |
468 KB |
Output is correct |
34 |
Runtime error |
105 ms |
123376 KB |
Execution killed with signal 11 |
35 |
Halted |
0 ms |
0 KB |
- |