#include "candies.h"
#include <bits/stdc++.h>
#define MAX 200001
#define INF LLONG_MAX
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ins insert
#define ff first
#define ss second
#define gett(x,m) get<m>(x)
#define all(a) a.begin(),a.end()
#define lb(a,b) lower_bound(all(a),b)
#define ub(a,b) upper_bound(all(a),b)
#define sortv(a) sort(all(a))
#define sorta(a,sz) sort(a,a+sz)
#define inputar(a,b){\
for(int i=0;i<b;i++){\
cin >> a[i];\
}\
}
#define inputvec(a,b){\
for(int i=0;i<b;i++){\
ll num;\
cin >> num;\
a.pb(num);\
}\
}
#define outputar(a,b){\
for(int i=0;i<b;i++){\
cout << a[i] << " ";\
}\
cout << "\n";\
}
#define outputvec(a){\
for(auto x:a){\
cout << x << " ";\
}\
cout << "\n";\
}
#define reset(a,n,v){\
for(int i=0;i<n;i++){\
a[i]=v;\
}\
}
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef tuple<ll,ll,ll> tll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef double db;
typedef long double ldb;
inline void USACO(string filename){
freopen((filename+".in").c_str(),"r",stdin);
freopen((filename+".out").c_str(),"w",stdout);
}
ll n,q,t=1,m,n2,m2,k,x,y,z,x2,y2,z2,res1=0,a[MAX],b[MAX],d[MAX];
struct segtree{
vector<int> mn,mx,lazy;
int sz;
void init(int n){
sz=1;
while(sz<n){
sz*=2;
}
mn.resize(2*sz,0);
mx.resize(2*sz,0);
lazy.resize(2*sz,0);
}
void propogate(int x,int lx,int rx){
if(rx-lx==1 || lazy[x]==0){
return;
}
mn[2*x+1]+=lazy[x];
mx[2*x+1]+=lazy[x];
mn[2*x+2]+=lazy[x];
mx[2*x+2]+=lazy[x];
lazy[x]=0;
}
ll get_max(){
return mx[0];
}
ll get_min(){
return mn[0];
}
void upd(int x,int lx,int rx,int l,int r,int v){
propogate(x,lx,rx);
if(rx<=l || lx>=r){
return;
}
if(rx==r && lx==l){
mn[x]+=v;
mx[x]+=v;
lazy[x]+=v;
return;
}
int m=(lx+rx)/2;
upd(2*x+1,lx,m,l,r,v);
upd(2*x+2,m,rx,l,r,v);
mn[x]=min(mn[2*x+1],mn[2*x+2]);
mx[x]=max(mx[2*x+1],mx[2*x+2]);
}
void upd(int l,int r,int v){
upd(0,0,sz,l,r,v);
}
};
vector<int> distribute_candies(vector<int> c, vector<int> l,
vector<int> r, vector<int> v) {
int n = c.size();
int q = v.size();
vector<int> s(n);
vector<vector<pii>> ops;
ops.resize(n+1);
for(int i=0;i<q;i++){
ops[l[i]].pb(mp(1,i));
ops[r[i]+1].pb(mp(2,i));
}
segtree st;
int sum=0;
st.init(q+1);
for(int i=0;i<n;i++){
for(auto x:ops[i]){
if(x.ff==1){
sum+=v[x.ss];
st.upd(x.ss+1,q,v[x.ss]);
}
else{
sum-=v[x.ss];
st.upd(x.ss+1,q,-v[x.ss]);
}
}
int mx,mn;
mx=st.get_max();
mn=st.get_min();
int res=sum;
if(mx-mn>c[i]){
res-=(mx-mn-c[i]);
}
mn=min(mn,res);
res-=mn;
//cout << mx << " " << mn << " " << sum << "\n";
s[i]=res;
}
return s;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
154 ms |
55868 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
