# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1012398 |
2024-07-02T05:54:03 Z |
12345678 |
Fish 3 (JOI24_fish3) |
C++17 |
|
382 ms |
57476 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int nx=3e5+5;
ll n, d, c[nx], q, l[nx], r[nx], res[nx], t[nx], sv[nx];
vector<ll> qrs[nx];
stack<pair<ll, ll>> st;
struct segtree
{
ll d[4*nx], lz[4*nx];
void pushlz(int l, int r, int i)
{
d[i]+=lz[i]*(r-l+1);
if (l==r) return lz[i]=0, void();
lz[2*i]+=lz[i];
lz[2*i+1]+=lz[i];
lz[i]=0;
}
void update(int l, int r, int i, int ql, int qr, ll vl)
{
pushlz(l, r, i);
if (qr<l||r<ql) return;
if (ql<=l&&r<=qr) return lz[i]+=vl, pushlz(l, r, i), void();
int md=(l+r)/2;
update(l, md ,2*i, ql, qr, vl);
update(md+1, r ,2*i+1, ql, qr, vl);
d[i]=d[2*i]+d[2*i+1];
}
ll query(int l, int r, int i, int ql, int qr)
{
pushlz(l, r, i);
if (qr<l||r<ql) return 0;
if (ql<=l&&r<=qr) return d[i];
int md=(l+r)/2;
return query(l, md, 2*i, ql, qr)+query(md+1, r, 2*i+1, ql, qr);
}
void show(int l, int r, int i)
{
pushlz(l, r, i);
if (l==r) cout<<l<<' '<<r<<' '<<d[i]<<'\n';
if (l==r) return;
int md=(l+r)/2;
show(l, md ,2*i);
show(md+1, r, 2*i+1);
}
} s;
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>n>>d;
for (int i=1; i<=n; i++) cin>>c[i];
for (int i=1; i<n; i++)
{
if (c[i]>c[i+1]) t[i]=(c[i]-c[i+1])/d+((c[i]-c[i+1])%d!=0);
}
for (int i=1; i<n; i++) if (c[i]<c[i+1]) sv[i]=(c[i+1]-c[i])/d;
cin>>q;
for (int i=1; i<=q; i++) cin>>l[i]>>r[i], qrs[r[i]].push_back(i);
st.push({LLONG_MAX, 0});
for (int i=1; i<=n; i++)
{
for (auto x:qrs[i])
{
if (s.query(1, n, 1, l[x], l[x])*d>c[l[x]]) res[x]=-1;
else res[x]=s.query(1, n, 1, l[x], r[x]-1);
}
if (t[i])
{
while (t[i]>0)
{
auto tmp=st.top();
st.pop();
if (tmp.first<=t[i])
{
t[i]-=tmp.first;
s.update(1, n, 1, tmp.second+1, i, tmp.first);
}
else
{
tmp.first-=t[i];
s.update(1,n, 1, tmp.second+1, i, t[i]);
t[i]=0;
st.push(tmp);
}
}
}
if (sv[i])
{
st.push({sv[i], i});
}
}
for (int i=1; i<=q; i++) cout<<res[i]<<'\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
8540 KB |
Output is correct |
2 |
Correct |
1 ms |
8540 KB |
Output is correct |
3 |
Correct |
2 ms |
7516 KB |
Output is correct |
4 |
Correct |
4 ms |
7924 KB |
Output is correct |
5 |
Correct |
3 ms |
8028 KB |
Output is correct |
6 |
Correct |
4 ms |
9052 KB |
Output is correct |
7 |
Correct |
3 ms |
7768 KB |
Output is correct |
8 |
Correct |
3 ms |
9048 KB |
Output is correct |
9 |
Correct |
3 ms |
8040 KB |
Output is correct |
10 |
Correct |
4 ms |
8028 KB |
Output is correct |
11 |
Correct |
3 ms |
8028 KB |
Output is correct |
12 |
Correct |
4 ms |
9052 KB |
Output is correct |
13 |
Correct |
3 ms |
8028 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
292 ms |
45900 KB |
Output is correct |
2 |
Correct |
286 ms |
44880 KB |
Output is correct |
3 |
Correct |
83 ms |
23376 KB |
Output is correct |
4 |
Correct |
210 ms |
49232 KB |
Output is correct |
5 |
Correct |
177 ms |
49232 KB |
Output is correct |
6 |
Correct |
231 ms |
44628 KB |
Output is correct |
7 |
Correct |
224 ms |
44628 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
137 ms |
24660 KB |
Output is correct |
2 |
Correct |
356 ms |
56912 KB |
Output is correct |
3 |
Correct |
376 ms |
56916 KB |
Output is correct |
4 |
Correct |
382 ms |
57020 KB |
Output is correct |
5 |
Correct |
367 ms |
56916 KB |
Output is correct |
6 |
Correct |
325 ms |
50516 KB |
Output is correct |
7 |
Correct |
314 ms |
50516 KB |
Output is correct |
8 |
Correct |
326 ms |
53840 KB |
Output is correct |
9 |
Correct |
365 ms |
53844 KB |
Output is correct |
10 |
Correct |
296 ms |
54872 KB |
Output is correct |
11 |
Correct |
290 ms |
55116 KB |
Output is correct |
12 |
Correct |
336 ms |
57424 KB |
Output is correct |
13 |
Correct |
341 ms |
57476 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
254 ms |
32340 KB |
Output is correct |
2 |
Correct |
304 ms |
41296 KB |
Output is correct |
3 |
Correct |
199 ms |
25164 KB |
Output is correct |
4 |
Correct |
298 ms |
41296 KB |
Output is correct |
5 |
Correct |
312 ms |
45904 KB |
Output is correct |
6 |
Correct |
355 ms |
47696 KB |
Output is correct |
7 |
Correct |
315 ms |
38172 KB |
Output is correct |
8 |
Correct |
336 ms |
46732 KB |
Output is correct |
9 |
Correct |
193 ms |
40440 KB |
Output is correct |
10 |
Correct |
188 ms |
41212 KB |
Output is correct |
11 |
Correct |
300 ms |
41296 KB |
Output is correct |
12 |
Correct |
209 ms |
40428 KB |
Output is correct |
13 |
Correct |
343 ms |
46672 KB |
Output is correct |
14 |
Correct |
247 ms |
43440 KB |
Output is correct |
15 |
Correct |
366 ms |
46652 KB |
Output is correct |
16 |
Correct |
229 ms |
43596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
8540 KB |
Output is correct |
2 |
Correct |
1 ms |
8540 KB |
Output is correct |
3 |
Correct |
2 ms |
7516 KB |
Output is correct |
4 |
Correct |
4 ms |
7924 KB |
Output is correct |
5 |
Correct |
3 ms |
8028 KB |
Output is correct |
6 |
Correct |
4 ms |
9052 KB |
Output is correct |
7 |
Correct |
3 ms |
7768 KB |
Output is correct |
8 |
Correct |
3 ms |
9048 KB |
Output is correct |
9 |
Correct |
3 ms |
8040 KB |
Output is correct |
10 |
Correct |
4 ms |
8028 KB |
Output is correct |
11 |
Correct |
3 ms |
8028 KB |
Output is correct |
12 |
Correct |
4 ms |
9052 KB |
Output is correct |
13 |
Correct |
3 ms |
8028 KB |
Output is correct |
14 |
Correct |
292 ms |
45900 KB |
Output is correct |
15 |
Correct |
286 ms |
44880 KB |
Output is correct |
16 |
Correct |
83 ms |
23376 KB |
Output is correct |
17 |
Correct |
210 ms |
49232 KB |
Output is correct |
18 |
Correct |
177 ms |
49232 KB |
Output is correct |
19 |
Correct |
231 ms |
44628 KB |
Output is correct |
20 |
Correct |
224 ms |
44628 KB |
Output is correct |
21 |
Correct |
137 ms |
24660 KB |
Output is correct |
22 |
Correct |
356 ms |
56912 KB |
Output is correct |
23 |
Correct |
376 ms |
56916 KB |
Output is correct |
24 |
Correct |
382 ms |
57020 KB |
Output is correct |
25 |
Correct |
367 ms |
56916 KB |
Output is correct |
26 |
Correct |
325 ms |
50516 KB |
Output is correct |
27 |
Correct |
314 ms |
50516 KB |
Output is correct |
28 |
Correct |
326 ms |
53840 KB |
Output is correct |
29 |
Correct |
365 ms |
53844 KB |
Output is correct |
30 |
Correct |
296 ms |
54872 KB |
Output is correct |
31 |
Correct |
290 ms |
55116 KB |
Output is correct |
32 |
Correct |
336 ms |
57424 KB |
Output is correct |
33 |
Correct |
341 ms |
57476 KB |
Output is correct |
34 |
Correct |
254 ms |
32340 KB |
Output is correct |
35 |
Correct |
304 ms |
41296 KB |
Output is correct |
36 |
Correct |
199 ms |
25164 KB |
Output is correct |
37 |
Correct |
298 ms |
41296 KB |
Output is correct |
38 |
Correct |
312 ms |
45904 KB |
Output is correct |
39 |
Correct |
355 ms |
47696 KB |
Output is correct |
40 |
Correct |
315 ms |
38172 KB |
Output is correct |
41 |
Correct |
336 ms |
46732 KB |
Output is correct |
42 |
Correct |
193 ms |
40440 KB |
Output is correct |
43 |
Correct |
188 ms |
41212 KB |
Output is correct |
44 |
Correct |
300 ms |
41296 KB |
Output is correct |
45 |
Correct |
209 ms |
40428 KB |
Output is correct |
46 |
Correct |
343 ms |
46672 KB |
Output is correct |
47 |
Correct |
247 ms |
43440 KB |
Output is correct |
48 |
Correct |
366 ms |
46652 KB |
Output is correct |
49 |
Correct |
229 ms |
43596 KB |
Output is correct |
50 |
Correct |
364 ms |
57232 KB |
Output is correct |
51 |
Correct |
306 ms |
50516 KB |
Output is correct |
52 |
Correct |
344 ms |
53892 KB |
Output is correct |
53 |
Correct |
326 ms |
54868 KB |
Output is correct |
54 |
Correct |
317 ms |
57468 KB |
Output is correct |
55 |
Correct |
373 ms |
56852 KB |
Output is correct |
56 |
Correct |
225 ms |
52560 KB |
Output is correct |
57 |
Correct |
209 ms |
49488 KB |
Output is correct |
58 |
Correct |
201 ms |
49492 KB |
Output is correct |
59 |
Correct |
341 ms |
54868 KB |
Output is correct |
60 |
Correct |
239 ms |
52476 KB |
Output is correct |
61 |
Correct |
270 ms |
54840 KB |
Output is correct |
62 |
Correct |
307 ms |
50004 KB |
Output is correct |
63 |
Correct |
380 ms |
57264 KB |
Output is correct |
64 |
Correct |
242 ms |
52560 KB |
Output is correct |