# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1007590 |
2024-06-25T08:31:21 Z |
batsukh2006 |
Fish 3 (JOI24_fish3) |
C++17 |
|
277 ms |
128488 KB |
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<map>
#include<string>
#include<algorithm>
#include<vector>
#include<string.h>
#include<utility>
#include<set>
#include<cmath>
#include<queue>
#include<deque>
#include<functional>
#include<stack>
#include<limits.h>
#include<iomanip>
#include<unordered_map>
using namespace std;
#define MOD 1000000007
#define int long long
#define endl '\n'
#define ff first
#define ss second
typedef pair<int,int> pp;
void solve(){
int n,d; cin>>n>>d;
vector<int> a(n+1);
for(int i=1; i<=n; i++) cin>>a[i];
vector<int> dp(n+1),pref(n+2),comp(n+1);
dp[n]=a[n];
for(int i=n-1; i>=1; i--){
if(a[i]>dp[i+1]){
comp[i]=((a[i]-dp[i+1])+(d-1))/d;
dp[i]=a[i]-((a[i]-dp[i+1])+(d-1))/d*d;
pref[i]=pref[i+1]+((a[i]-dp[i+1])+(d-1))/d;
}else{
comp[i]=0;
dp[i]=a[i];
pref[i]=pref[i+1];
}
}
stack<int> s;
s.push(0);
vector<vector<pp> > p(n+1,vector<pp>(20));
for(int i=1; i<=n; i++){
while(s.size()>1&&comp[s.top()]>=comp[i]) s.pop();
p[i][0]=make_pair(s.top(),comp[i]*(i-s.top()));
s.push(i);
}
for(int i=1; i<20; i++){
for(int j=1; j<=n; j++){
p[j][i].ff=p[p[j][i-1].ff][i-1].ff;
p[j][i].ss=p[j][i-1].ss+p[p[j][i-1].ff][i-1].ss;
}
}
int q; cin>>q;
while(q--){
int l,r; cin>>l>>r;
int cur=r,sum=0;
int ans=pref[l]-pref[r+1];
for(int i=19; i>=0; i--){
if(p[cur][i].ff>=l){
sum+=p[cur][i].ss;
cur=p[cur][i].ff;
}
}
sum+=comp[cur]*(cur-l+1);
if(dp[l]+comp[cur]*d<0) cout<<-1<<endl;
else cout<<ans-sum<<endl;
}
}
signed main(){
// freopen("hps.in", "r", stdin);
// freopen("hps.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;
// cin>>t;
while(t--){
solve();
cout<<endl;
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
3 ms |
1684 KB |
Output is correct |
5 |
Correct |
2 ms |
1628 KB |
Output is correct |
6 |
Correct |
1 ms |
1116 KB |
Output is correct |
7 |
Correct |
1 ms |
1112 KB |
Output is correct |
8 |
Correct |
2 ms |
1636 KB |
Output is correct |
9 |
Correct |
2 ms |
1616 KB |
Output is correct |
10 |
Correct |
2 ms |
1624 KB |
Output is correct |
11 |
Correct |
2 ms |
1628 KB |
Output is correct |
12 |
Correct |
2 ms |
1628 KB |
Output is correct |
13 |
Correct |
1 ms |
1628 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
241 ms |
121680 KB |
Output is correct |
2 |
Correct |
234 ms |
121112 KB |
Output is correct |
3 |
Correct |
56 ms |
4692 KB |
Output is correct |
4 |
Correct |
225 ms |
120656 KB |
Output is correct |
5 |
Correct |
230 ms |
120856 KB |
Output is correct |
6 |
Correct |
237 ms |
120656 KB |
Output is correct |
7 |
Correct |
232 ms |
120660 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
68 ms |
8276 KB |
Output is correct |
2 |
Correct |
267 ms |
128388 KB |
Output is correct |
3 |
Correct |
277 ms |
128340 KB |
Output is correct |
4 |
Correct |
258 ms |
128336 KB |
Output is correct |
5 |
Correct |
259 ms |
128488 KB |
Output is correct |
6 |
Correct |
231 ms |
121900 KB |
Output is correct |
7 |
Correct |
230 ms |
122088 KB |
Output is correct |
8 |
Correct |
245 ms |
125264 KB |
Output is correct |
9 |
Correct |
254 ms |
125292 KB |
Output is correct |
10 |
Correct |
237 ms |
123628 KB |
Output is correct |
11 |
Correct |
239 ms |
123728 KB |
Output is correct |
12 |
Correct |
261 ms |
126800 KB |
Output is correct |
13 |
Correct |
250 ms |
126804 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
212 ms |
101872 KB |
Output is correct |
2 |
Correct |
226 ms |
121776 KB |
Output is correct |
3 |
Correct |
96 ms |
31576 KB |
Output is correct |
4 |
Correct |
244 ms |
125008 KB |
Output is correct |
5 |
Correct |
217 ms |
113728 KB |
Output is correct |
6 |
Correct |
248 ms |
128336 KB |
Output is correct |
7 |
Correct |
210 ms |
102864 KB |
Output is correct |
8 |
Correct |
248 ms |
128236 KB |
Output is correct |
9 |
Correct |
219 ms |
120912 KB |
Output is correct |
10 |
Correct |
221 ms |
120656 KB |
Output is correct |
11 |
Correct |
225 ms |
125008 KB |
Output is correct |
12 |
Correct |
228 ms |
124364 KB |
Output is correct |
13 |
Correct |
250 ms |
128060 KB |
Output is correct |
14 |
Correct |
224 ms |
124076 KB |
Output is correct |
15 |
Correct |
250 ms |
128080 KB |
Output is correct |
16 |
Correct |
234 ms |
123984 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
3 ms |
1684 KB |
Output is correct |
5 |
Correct |
2 ms |
1628 KB |
Output is correct |
6 |
Correct |
1 ms |
1116 KB |
Output is correct |
7 |
Correct |
1 ms |
1112 KB |
Output is correct |
8 |
Correct |
2 ms |
1636 KB |
Output is correct |
9 |
Correct |
2 ms |
1616 KB |
Output is correct |
10 |
Correct |
2 ms |
1624 KB |
Output is correct |
11 |
Correct |
2 ms |
1628 KB |
Output is correct |
12 |
Correct |
2 ms |
1628 KB |
Output is correct |
13 |
Correct |
1 ms |
1628 KB |
Output is correct |
14 |
Correct |
241 ms |
121680 KB |
Output is correct |
15 |
Correct |
234 ms |
121112 KB |
Output is correct |
16 |
Correct |
56 ms |
4692 KB |
Output is correct |
17 |
Correct |
225 ms |
120656 KB |
Output is correct |
18 |
Correct |
230 ms |
120856 KB |
Output is correct |
19 |
Correct |
237 ms |
120656 KB |
Output is correct |
20 |
Correct |
232 ms |
120660 KB |
Output is correct |
21 |
Correct |
68 ms |
8276 KB |
Output is correct |
22 |
Correct |
267 ms |
128388 KB |
Output is correct |
23 |
Correct |
277 ms |
128340 KB |
Output is correct |
24 |
Correct |
258 ms |
128336 KB |
Output is correct |
25 |
Correct |
259 ms |
128488 KB |
Output is correct |
26 |
Correct |
231 ms |
121900 KB |
Output is correct |
27 |
Correct |
230 ms |
122088 KB |
Output is correct |
28 |
Correct |
245 ms |
125264 KB |
Output is correct |
29 |
Correct |
254 ms |
125292 KB |
Output is correct |
30 |
Correct |
237 ms |
123628 KB |
Output is correct |
31 |
Correct |
239 ms |
123728 KB |
Output is correct |
32 |
Correct |
261 ms |
126800 KB |
Output is correct |
33 |
Correct |
250 ms |
126804 KB |
Output is correct |
34 |
Correct |
212 ms |
101872 KB |
Output is correct |
35 |
Correct |
226 ms |
121776 KB |
Output is correct |
36 |
Correct |
96 ms |
31576 KB |
Output is correct |
37 |
Correct |
244 ms |
125008 KB |
Output is correct |
38 |
Correct |
217 ms |
113728 KB |
Output is correct |
39 |
Correct |
248 ms |
128336 KB |
Output is correct |
40 |
Correct |
210 ms |
102864 KB |
Output is correct |
41 |
Correct |
248 ms |
128236 KB |
Output is correct |
42 |
Correct |
219 ms |
120912 KB |
Output is correct |
43 |
Correct |
221 ms |
120656 KB |
Output is correct |
44 |
Correct |
225 ms |
125008 KB |
Output is correct |
45 |
Correct |
228 ms |
124364 KB |
Output is correct |
46 |
Correct |
250 ms |
128060 KB |
Output is correct |
47 |
Correct |
224 ms |
124076 KB |
Output is correct |
48 |
Correct |
250 ms |
128080 KB |
Output is correct |
49 |
Correct |
234 ms |
123984 KB |
Output is correct |
50 |
Correct |
260 ms |
128340 KB |
Output is correct |
51 |
Correct |
248 ms |
122084 KB |
Output is correct |
52 |
Correct |
251 ms |
125100 KB |
Output is correct |
53 |
Correct |
225 ms |
123732 KB |
Output is correct |
54 |
Correct |
247 ms |
126940 KB |
Output is correct |
55 |
Correct |
260 ms |
128336 KB |
Output is correct |
56 |
Correct |
215 ms |
123880 KB |
Output is correct |
57 |
Correct |
225 ms |
120872 KB |
Output is correct |
58 |
Correct |
214 ms |
121096 KB |
Output is correct |
59 |
Correct |
229 ms |
126136 KB |
Output is correct |
60 |
Correct |
269 ms |
124244 KB |
Output is correct |
61 |
Correct |
239 ms |
123728 KB |
Output is correct |
62 |
Correct |
231 ms |
123744 KB |
Output is correct |
63 |
Correct |
240 ms |
126548 KB |
Output is correct |
64 |
Correct |
238 ms |
123984 KB |
Output is correct |