# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
538233 |
2022-03-16T11:14:25 Z |
AdamGS |
Peru (RMI20_peru) |
C++17 |
|
600 ms |
88448 KB |
#include "peru.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll MOD=1e9+7, LIM=25e5+7, INF=1e18+7;
ll dp[LIM], tr[4*LIM], trm[4*LIM], N=1, li;
vector<pair<ll,int>>V;
ll cnt(int l, int r) {
l+=N; r+=N;
ll ans=max(tr[l], tr[r]);
while(l/2!=r/2) {
if(l%2==0) ans=max(ans, tr[l+1]);
if(r%2==1) ans=max(ans, tr[r-1]);
l/=2; r/=2;
}
return ans;
}
ll cnt2(int l, int r) {
if(l>r) return INF;
l+=N; r+=N;
ll ans=min(trm[l], trm[r]);
while(l/2!=r/2) {
if(l%2==0) ans=min(ans, trm[l+1]);
if(r%2==1) ans=min(ans, trm[r-1]);
l/=2; r/=2;
}
return ans;
}
void upd(int v, ll x) {
v+=N;
trm[v]=x;
v/=2;
while(v) {
trm[v]=min(trm[2*v], trm[2*v+1]);
v/=2;
}
}
int solve(int n, int k, int* v){
while(N<n) N*=2;
rep(i, n) tr[N+i]=v[i];
for(int i=N-1; i>=0; --i) tr[i]=max(tr[2*i], tr[2*i+1]);
rep(i, k) {
dp[i]=cnt(0, i);
while(V.size() && v[i]>=V.back().st) {
V.pop_back();
li=min(li, (long long)V.size());
}
if(V.size()) upd(V.size(), v[i]+dp[V.back().nd]);
V.pb({v[i], i});
}
for(int i=k; i<n; ++i) {
while(V.size() && v[i]>=V.back().st) {
V.pop_back();
li=min(li, (long long)V.size());
}
if(V.size()) upd(V.size(), v[i]+dp[V.back().nd]);
V.pb({v[i], i});
dp[i]=dp[i-k]+cnt(i-k+1, i);
while(li<V.size() && V[li].nd<=i-k) ++li;
dp[i]=min(dp[i], cnt2(li+1, V.size()-1));
}
ll ans=0;
rep(i, n) ans=(ans*23+dp[i])%MOD;
return ans;
}
Compilation message
peru.cpp: In function 'int solve(int, int, int*)':
peru.cpp:64:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | while(li<V.size() && V[li].nd<=i-k) ++li;
| ~~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
76 ms |
12656 KB |
Output is correct |
16 |
Correct |
76 ms |
12756 KB |
Output is correct |
17 |
Correct |
89 ms |
13056 KB |
Output is correct |
18 |
Correct |
76 ms |
12380 KB |
Output is correct |
19 |
Correct |
80 ms |
12316 KB |
Output is correct |
20 |
Correct |
82 ms |
12364 KB |
Output is correct |
21 |
Correct |
82 ms |
12780 KB |
Output is correct |
22 |
Correct |
85 ms |
13324 KB |
Output is correct |
23 |
Correct |
80 ms |
13340 KB |
Output is correct |
24 |
Correct |
78 ms |
12892 KB |
Output is correct |
25 |
Correct |
78 ms |
13676 KB |
Output is correct |
26 |
Correct |
75 ms |
12724 KB |
Output is correct |
27 |
Correct |
76 ms |
12700 KB |
Output is correct |
28 |
Correct |
80 ms |
12900 KB |
Output is correct |
29 |
Correct |
81 ms |
12748 KB |
Output is correct |
30 |
Correct |
76 ms |
12768 KB |
Output is correct |
31 |
Correct |
74 ms |
12656 KB |
Output is correct |
32 |
Correct |
80 ms |
12888 KB |
Output is correct |
33 |
Correct |
77 ms |
12864 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
76 ms |
12656 KB |
Output is correct |
2 |
Correct |
76 ms |
12756 KB |
Output is correct |
3 |
Correct |
89 ms |
13056 KB |
Output is correct |
4 |
Correct |
76 ms |
12380 KB |
Output is correct |
5 |
Correct |
80 ms |
12316 KB |
Output is correct |
6 |
Correct |
82 ms |
12364 KB |
Output is correct |
7 |
Correct |
82 ms |
12780 KB |
Output is correct |
8 |
Correct |
85 ms |
13324 KB |
Output is correct |
9 |
Correct |
80 ms |
13340 KB |
Output is correct |
10 |
Correct |
78 ms |
12892 KB |
Output is correct |
11 |
Correct |
78 ms |
13676 KB |
Output is correct |
12 |
Correct |
75 ms |
12724 KB |
Output is correct |
13 |
Correct |
76 ms |
12700 KB |
Output is correct |
14 |
Correct |
80 ms |
12900 KB |
Output is correct |
15 |
Correct |
81 ms |
12748 KB |
Output is correct |
16 |
Correct |
76 ms |
12768 KB |
Output is correct |
17 |
Correct |
74 ms |
12656 KB |
Output is correct |
18 |
Correct |
80 ms |
12888 KB |
Output is correct |
19 |
Correct |
77 ms |
12864 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
340 KB |
Output is correct |
28 |
Correct |
1 ms |
340 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
1 ms |
340 KB |
Output is correct |
31 |
Correct |
1 ms |
340 KB |
Output is correct |
32 |
Correct |
1 ms |
340 KB |
Output is correct |
33 |
Correct |
1 ms |
340 KB |
Output is correct |
34 |
Correct |
519 ms |
83948 KB |
Output is correct |
35 |
Correct |
540 ms |
85164 KB |
Output is correct |
36 |
Correct |
545 ms |
85108 KB |
Output is correct |
37 |
Correct |
598 ms |
85864 KB |
Output is correct |
38 |
Correct |
543 ms |
85316 KB |
Output is correct |
39 |
Correct |
550 ms |
86072 KB |
Output is correct |
40 |
Correct |
559 ms |
88448 KB |
Output is correct |
41 |
Correct |
561 ms |
87352 KB |
Output is correct |
42 |
Correct |
536 ms |
87152 KB |
Output is correct |
43 |
Correct |
214 ms |
30944 KB |
Output is correct |
44 |
Correct |
284 ms |
48412 KB |
Output is correct |
45 |
Correct |
289 ms |
48468 KB |
Output is correct |
46 |
Correct |
310 ms |
48412 KB |
Output is correct |
47 |
Correct |
595 ms |
86700 KB |
Output is correct |
48 |
Execution timed out |
614 ms |
87856 KB |
Time limit exceeded |
49 |
Halted |
0 ms |
0 KB |
- |