#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;
#define ll long long
ll sum[4*maxn],mx[4*maxn],mn[4*maxn];
void update(int l,int r,int id,int p,int val){
if(l==r){
if(sum[id]) sum[id]=0;
else sum[id]=val;
mx[id]=max(0LL,sum[id]);
mn[id]=min(0LL,sum[id]);
return;
}
int mid=(l+r)>>1;
if(p<=mid) update(l,mid,id<<1,p,val);
else update(mid+1,r,id<<1|1,p,val);
sum[id]=sum[id<<1]+sum[id<<1|1];
mx[id]=max(mx[id<<1],sum[id<<1]+mx[id<<1|1]);
mn[id]=min(mn[id<<1],sum[id<<1]+mn[id<<1|1]);
}
int query(int l,int r,int id,int c){
if(l==r) return min(max(sum[id],0LL),(ll)c);
int mid=(l+r)>>1;
if(mx[id<<1|1]-mn[id<<1|1]>c) return query(mid+1,r,id<<1|1,c);
int cc=query(l,mid,id<<1,c);
if(cc+mx[id<<1|1]>c) return c+sum[id<<1|1]-mx[id<<1|1];
if(cc+mn[id<<1|1]<0) return sum[id<<1|1]-mn[id<<1|1];
return cc+sum[id<<1|1];
}
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v) {
int n=(int)c.size(),q=(int)l.size();
vector<int> a(n);
vector<vector<int>> g(n+1);
for(int i=0;i<q;i++) g[l[i]].push_back(i+1),g[r[i]+1].push_back(-i-1);
for(int i=0;i<n;i++){
for(int id:g[i]){
int p=abs(id)-1;
update(0,q-1,1,p,v[p]);
}
a[i]=query(0,q-1,1,c[i]);
}
return a;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
3 |
Correct |
2 ms |
2652 KB |
Output is correct |
4 |
Correct |
1 ms |
2648 KB |
Output is correct |
5 |
Correct |
2 ms |
2652 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
193 ms |
34900 KB |
Output is correct |
2 |
Correct |
181 ms |
34024 KB |
Output is correct |
3 |
Correct |
199 ms |
33876 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
108 ms |
22640 KB |
Output is correct |
3 |
Correct |
39 ms |
9824 KB |
Output is correct |
4 |
Correct |
181 ms |
35944 KB |
Output is correct |
5 |
Correct |
193 ms |
36180 KB |
Output is correct |
6 |
Correct |
210 ms |
36692 KB |
Output is correct |
7 |
Correct |
179 ms |
35928 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
3 |
Correct |
55 ms |
23900 KB |
Output is correct |
4 |
Correct |
37 ms |
10632 KB |
Output is correct |
5 |
Correct |
98 ms |
29632 KB |
Output is correct |
6 |
Correct |
99 ms |
30384 KB |
Output is correct |
7 |
Correct |
96 ms |
30912 KB |
Output is correct |
8 |
Correct |
96 ms |
29632 KB |
Output is correct |
9 |
Correct |
99 ms |
31164 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
3 |
Correct |
2 ms |
2652 KB |
Output is correct |
4 |
Correct |
1 ms |
2648 KB |
Output is correct |
5 |
Correct |
2 ms |
2652 KB |
Output is correct |
6 |
Correct |
193 ms |
34900 KB |
Output is correct |
7 |
Correct |
181 ms |
34024 KB |
Output is correct |
8 |
Correct |
199 ms |
33876 KB |
Output is correct |
9 |
Correct |
1 ms |
344 KB |
Output is correct |
10 |
Correct |
108 ms |
22640 KB |
Output is correct |
11 |
Correct |
39 ms |
9824 KB |
Output is correct |
12 |
Correct |
181 ms |
35944 KB |
Output is correct |
13 |
Correct |
193 ms |
36180 KB |
Output is correct |
14 |
Correct |
210 ms |
36692 KB |
Output is correct |
15 |
Correct |
179 ms |
35928 KB |
Output is correct |
16 |
Correct |
1 ms |
2392 KB |
Output is correct |
17 |
Correct |
1 ms |
2396 KB |
Output is correct |
18 |
Correct |
55 ms |
23900 KB |
Output is correct |
19 |
Correct |
37 ms |
10632 KB |
Output is correct |
20 |
Correct |
98 ms |
29632 KB |
Output is correct |
21 |
Correct |
99 ms |
30384 KB |
Output is correct |
22 |
Correct |
96 ms |
30912 KB |
Output is correct |
23 |
Correct |
96 ms |
29632 KB |
Output is correct |
24 |
Correct |
99 ms |
31164 KB |
Output is correct |
25 |
Correct |
1 ms |
2392 KB |
Output is correct |
26 |
Correct |
39 ms |
8780 KB |
Output is correct |
27 |
Correct |
102 ms |
22464 KB |
Output is correct |
28 |
Correct |
179 ms |
34404 KB |
Output is correct |
29 |
Correct |
178 ms |
34900 KB |
Output is correct |
30 |
Correct |
184 ms |
35156 KB |
Output is correct |
31 |
Correct |
184 ms |
35668 KB |
Output is correct |
32 |
Correct |
180 ms |
35680 KB |
Output is correct |