#include <bits/stdc++.h>
#define pb push_back
typedef long long ll;
using namespace std;
const ll INF = (ll)(1e18);
struct segtree
{
vector<ll> smx, smn, sum;
int N;
segtree()
{
N = 1<<18;
smx.assign(2*N,0);
smn.assign(2*N,0);
sum.assign(2*N,0);
}
void upd(ll v, int t, int node, int lx, int rx)
{
if(rx-lx==1)
{
smx[node] = max(0LL, v);
smn[node] = min(0LL, v);
sum[node] = v;
return;
}
int mid = (lx+rx)/2;
if(t<mid) upd(v, t, 2*node, lx, mid);
else upd(v, t, 2*node+1, mid, rx);
sum[node] = sum[2*node]+sum[2*node+1];
smx[node] = max(smx[2*node],sum[2*node]+smx[2*node+1]);
smn[node] = min(smn[2*node],sum[2*node]+smn[2*node+1]);
}
ll get(ll c,int node, int lx, int rx)
{
if(rx-lx==1) return min(max(sum[node], 0LL), c);
int mid = (lx+rx)/2;
if(smx[2*node+1]-smn[2*node+1]>c) return get(c, 2*node+1, mid, rx);
ll a = get(c, 2*node, lx, mid);
if(a+smx[2*node+1]>c) return c-(smx[2*node+1]-sum[2*node+1]);
if(a+smn[2*node+1]<0) return sum[2*node+1]-smn[2*node+1];
return a+sum[2*node+1];
}
} st;
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v)
{
int N=c.size(), Q=l.size();
vector<int> final_A; // final array
vector<vector<int>> q(N+1); // q[i] store update at pos i
// +1 to remove ambiguity of index 0
for (int i=0; i<Q; i++) q[l[i]].pb(i+1), q[r[i]+1].pb(-(i+1));
for (int i=0; i<N; i++)
{
for (auto j:q[i])
{
// j is the update position
if (j>0) --j, st.upd(v[j], j, 1, 0, Q);
else j=-j-1, st.upd(0, j, 1, 0, Q);
}
final_A.pb(st.get(c[i], 1, 0, Q));
}
return final_A;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
12620 KB |
Output is correct |
2 |
Correct |
6 ms |
12620 KB |
Output is correct |
3 |
Correct |
7 ms |
12620 KB |
Output is correct |
4 |
Correct |
8 ms |
12620 KB |
Output is correct |
5 |
Correct |
9 ms |
12760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
425 ms |
30420 KB |
Output is correct |
2 |
Correct |
485 ms |
30656 KB |
Output is correct |
3 |
Correct |
454 ms |
30524 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
12620 KB |
Output is correct |
2 |
Correct |
253 ms |
19668 KB |
Output is correct |
3 |
Correct |
78 ms |
20156 KB |
Output is correct |
4 |
Correct |
465 ms |
30276 KB |
Output is correct |
5 |
Correct |
465 ms |
30236 KB |
Output is correct |
6 |
Correct |
451 ms |
30268 KB |
Output is correct |
7 |
Correct |
443 ms |
30280 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
12620 KB |
Output is correct |
2 |
Correct |
6 ms |
12636 KB |
Output is correct |
3 |
Correct |
123 ms |
19064 KB |
Output is correct |
4 |
Correct |
73 ms |
20064 KB |
Output is correct |
5 |
Correct |
200 ms |
26624 KB |
Output is correct |
6 |
Correct |
200 ms |
26692 KB |
Output is correct |
7 |
Correct |
207 ms |
26672 KB |
Output is correct |
8 |
Correct |
214 ms |
26656 KB |
Output is correct |
9 |
Correct |
213 ms |
26656 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
12620 KB |
Output is correct |
2 |
Correct |
6 ms |
12620 KB |
Output is correct |
3 |
Correct |
7 ms |
12620 KB |
Output is correct |
4 |
Correct |
8 ms |
12620 KB |
Output is correct |
5 |
Correct |
9 ms |
12760 KB |
Output is correct |
6 |
Correct |
425 ms |
30420 KB |
Output is correct |
7 |
Correct |
485 ms |
30656 KB |
Output is correct |
8 |
Correct |
454 ms |
30524 KB |
Output is correct |
9 |
Correct |
6 ms |
12620 KB |
Output is correct |
10 |
Correct |
253 ms |
19668 KB |
Output is correct |
11 |
Correct |
78 ms |
20156 KB |
Output is correct |
12 |
Correct |
465 ms |
30276 KB |
Output is correct |
13 |
Correct |
465 ms |
30236 KB |
Output is correct |
14 |
Correct |
451 ms |
30268 KB |
Output is correct |
15 |
Correct |
443 ms |
30280 KB |
Output is correct |
16 |
Correct |
6 ms |
12620 KB |
Output is correct |
17 |
Correct |
6 ms |
12636 KB |
Output is correct |
18 |
Correct |
123 ms |
19064 KB |
Output is correct |
19 |
Correct |
73 ms |
20064 KB |
Output is correct |
20 |
Correct |
200 ms |
26624 KB |
Output is correct |
21 |
Correct |
200 ms |
26692 KB |
Output is correct |
22 |
Correct |
207 ms |
26672 KB |
Output is correct |
23 |
Correct |
214 ms |
26656 KB |
Output is correct |
24 |
Correct |
213 ms |
26656 KB |
Output is correct |
25 |
Correct |
6 ms |
12620 KB |
Output is correct |
26 |
Correct |
78 ms |
20412 KB |
Output is correct |
27 |
Correct |
262 ms |
19916 KB |
Output is correct |
28 |
Correct |
456 ms |
30488 KB |
Output is correct |
29 |
Correct |
428 ms |
30504 KB |
Output is correct |
30 |
Correct |
440 ms |
30692 KB |
Output is correct |
31 |
Correct |
445 ms |
30628 KB |
Output is correct |
32 |
Correct |
435 ms |
30528 KB |
Output is correct |