# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
990673 |
2024-05-31T01:27:02 Z |
starchan |
Fish 3 (JOI24_fish3) |
C++17 |
|
551 ms |
111956 KB |
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in array<int, 2>
#define pb push_back
#define pob pop_back
#define INF (int)1e17
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
const int LOGM = 19;
const int MX = 3e5+5;
signed main()
{
fast();
int n, d;
cin >> n >> d;
vector<int> c(n+1); vector<int> off(n+1, 0);
for(int i = 1; i <= n; i++)
cin >> c[i];
vector<int> a(n+1), pref(n+1, 0); pref[1] = a[1] = c[1]/d;
for(int i = 2; i <= n; i++)
{
off[i] = off[i-1] + ((c[i]%d) < (c[i-1]%d));
a[i] = (c[i]/d) - off[i];
pref[i] = a[i] + pref[i-1];
}
//immediate left that is smaller.
int L[LOGM][n+1]; L[0][0] = 0; a[0] = -INF; int S[LOGM][n+1]; S[0][0] = 0;
for(int i = 1; i <= n; i++)
{
L[0][i] = i-1;
while(a[L[0][i]] >= a[i])
L[0][i] = L[0][L[0][i]];
S[0][i] = a[i]*(i-L[0][i]);
}
for(int i = 1; i < LOGM; i++)
{
for(int j = 0; j <= n; j++)
{
L[i][j] = L[i-1][L[i-1][j]];
S[i][j] = S[i-1][j]+S[i-1][L[i-1][j]];
}
}
int q; cin >> q;
while(q--)
{
int l, r;
cin >> l >> r;
int SS = pref[r]-pref[l-1];
for(int i = LOGM-1; i >= 0; i--)
{
if(L[i][r] >= l)
{
SS-=S[i][r];
r = L[i][r];
}
}
SS-=(a[r]*(r-l+1));
if(a[r] < (-off[l]))
SS = -1;
cout << SS << "\n";
}
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 |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
2 ms |
1372 KB |
Output is correct |
5 |
Correct |
2 ms |
1372 KB |
Output is correct |
6 |
Correct |
2 ms |
1116 KB |
Output is correct |
7 |
Correct |
2 ms |
860 KB |
Output is correct |
8 |
Correct |
2 ms |
1368 KB |
Output is correct |
9 |
Correct |
2 ms |
1372 KB |
Output is correct |
10 |
Correct |
2 ms |
1368 KB |
Output is correct |
11 |
Correct |
2 ms |
1372 KB |
Output is correct |
12 |
Correct |
2 ms |
1372 KB |
Output is correct |
13 |
Correct |
1 ms |
1372 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
192 ms |
105300 KB |
Output is correct |
2 |
Correct |
188 ms |
104528 KB |
Output is correct |
3 |
Correct |
46 ms |
4436 KB |
Output is correct |
4 |
Correct |
174 ms |
104276 KB |
Output is correct |
5 |
Correct |
177 ms |
104324 KB |
Output is correct |
6 |
Correct |
177 ms |
104272 KB |
Output is correct |
7 |
Correct |
173 ms |
104308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
60 ms |
8252 KB |
Output is correct |
2 |
Correct |
207 ms |
111952 KB |
Output is correct |
3 |
Correct |
224 ms |
111952 KB |
Output is correct |
4 |
Correct |
217 ms |
111952 KB |
Output is correct |
5 |
Correct |
238 ms |
111952 KB |
Output is correct |
6 |
Correct |
205 ms |
105568 KB |
Output is correct |
7 |
Correct |
199 ms |
105588 KB |
Output is correct |
8 |
Correct |
234 ms |
108896 KB |
Output is correct |
9 |
Correct |
225 ms |
108880 KB |
Output is correct |
10 |
Correct |
550 ms |
107320 KB |
Output is correct |
11 |
Correct |
551 ms |
107276 KB |
Output is correct |
12 |
Correct |
495 ms |
110508 KB |
Output is correct |
13 |
Correct |
485 ms |
110364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
157 ms |
88144 KB |
Output is correct |
2 |
Correct |
181 ms |
105428 KB |
Output is correct |
3 |
Correct |
82 ms |
27988 KB |
Output is correct |
4 |
Correct |
179 ms |
108568 KB |
Output is correct |
5 |
Correct |
182 ms |
99408 KB |
Output is correct |
6 |
Correct |
190 ms |
111948 KB |
Output is correct |
7 |
Correct |
166 ms |
89940 KB |
Output is correct |
8 |
Correct |
186 ms |
111700 KB |
Output is correct |
9 |
Correct |
170 ms |
104416 KB |
Output is correct |
10 |
Correct |
163 ms |
104272 KB |
Output is correct |
11 |
Correct |
185 ms |
108576 KB |
Output is correct |
12 |
Correct |
181 ms |
107816 KB |
Output is correct |
13 |
Correct |
183 ms |
111696 KB |
Output is correct |
14 |
Correct |
179 ms |
107600 KB |
Output is correct |
15 |
Correct |
186 ms |
111696 KB |
Output is correct |
16 |
Correct |
181 ms |
107600 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 |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
2 ms |
1372 KB |
Output is correct |
5 |
Correct |
2 ms |
1372 KB |
Output is correct |
6 |
Correct |
2 ms |
1116 KB |
Output is correct |
7 |
Correct |
2 ms |
860 KB |
Output is correct |
8 |
Correct |
2 ms |
1368 KB |
Output is correct |
9 |
Correct |
2 ms |
1372 KB |
Output is correct |
10 |
Correct |
2 ms |
1368 KB |
Output is correct |
11 |
Correct |
2 ms |
1372 KB |
Output is correct |
12 |
Correct |
2 ms |
1372 KB |
Output is correct |
13 |
Correct |
1 ms |
1372 KB |
Output is correct |
14 |
Correct |
192 ms |
105300 KB |
Output is correct |
15 |
Correct |
188 ms |
104528 KB |
Output is correct |
16 |
Correct |
46 ms |
4436 KB |
Output is correct |
17 |
Correct |
174 ms |
104276 KB |
Output is correct |
18 |
Correct |
177 ms |
104324 KB |
Output is correct |
19 |
Correct |
177 ms |
104272 KB |
Output is correct |
20 |
Correct |
173 ms |
104308 KB |
Output is correct |
21 |
Correct |
60 ms |
8252 KB |
Output is correct |
22 |
Correct |
207 ms |
111952 KB |
Output is correct |
23 |
Correct |
224 ms |
111952 KB |
Output is correct |
24 |
Correct |
217 ms |
111952 KB |
Output is correct |
25 |
Correct |
238 ms |
111952 KB |
Output is correct |
26 |
Correct |
205 ms |
105568 KB |
Output is correct |
27 |
Correct |
199 ms |
105588 KB |
Output is correct |
28 |
Correct |
234 ms |
108896 KB |
Output is correct |
29 |
Correct |
225 ms |
108880 KB |
Output is correct |
30 |
Correct |
550 ms |
107320 KB |
Output is correct |
31 |
Correct |
551 ms |
107276 KB |
Output is correct |
32 |
Correct |
495 ms |
110508 KB |
Output is correct |
33 |
Correct |
485 ms |
110364 KB |
Output is correct |
34 |
Correct |
157 ms |
88144 KB |
Output is correct |
35 |
Correct |
181 ms |
105428 KB |
Output is correct |
36 |
Correct |
82 ms |
27988 KB |
Output is correct |
37 |
Correct |
179 ms |
108568 KB |
Output is correct |
38 |
Correct |
182 ms |
99408 KB |
Output is correct |
39 |
Correct |
190 ms |
111948 KB |
Output is correct |
40 |
Correct |
166 ms |
89940 KB |
Output is correct |
41 |
Correct |
186 ms |
111700 KB |
Output is correct |
42 |
Correct |
170 ms |
104416 KB |
Output is correct |
43 |
Correct |
163 ms |
104272 KB |
Output is correct |
44 |
Correct |
185 ms |
108576 KB |
Output is correct |
45 |
Correct |
181 ms |
107816 KB |
Output is correct |
46 |
Correct |
183 ms |
111696 KB |
Output is correct |
47 |
Correct |
179 ms |
107600 KB |
Output is correct |
48 |
Correct |
186 ms |
111696 KB |
Output is correct |
49 |
Correct |
181 ms |
107600 KB |
Output is correct |
50 |
Correct |
208 ms |
111956 KB |
Output is correct |
51 |
Correct |
192 ms |
105552 KB |
Output is correct |
52 |
Correct |
207 ms |
108880 KB |
Output is correct |
53 |
Correct |
493 ms |
107280 KB |
Output is correct |
54 |
Correct |
453 ms |
110420 KB |
Output is correct |
55 |
Correct |
208 ms |
111952 KB |
Output is correct |
56 |
Correct |
176 ms |
107604 KB |
Output is correct |
57 |
Correct |
177 ms |
104276 KB |
Output is correct |
58 |
Correct |
180 ms |
104272 KB |
Output is correct |
59 |
Correct |
208 ms |
109912 KB |
Output is correct |
60 |
Correct |
179 ms |
107680 KB |
Output is correct |
61 |
Correct |
474 ms |
107312 KB |
Output is correct |
62 |
Correct |
177 ms |
107348 KB |
Output is correct |
63 |
Correct |
473 ms |
110672 KB |
Output is correct |
64 |
Correct |
179 ms |
107600 KB |
Output is correct |