#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(x) x.begin(),x.end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define vf first
#define vs second
vector<int> cap;
struct Seg {
vector<ll> lazy , set_val , val;
int siz;
void init(int n){
siz = 1;
while(siz < n)siz *= 2;
lazy.assign(siz * 2 , 0);
set_val.assign(siz * 2 , -1);
val.assign(siz * 2 , 0);
}
void push(int x){
if(set_val[x] != -1){
set_val[2*x+1] = set_val[x];
set_val[2*x+2] = set_val[x];
lazy[2*x+1] = lazy[2*x+2] = lazy[x];
lazy[x] = 0;
set_val[x] = -1;
}
else {
lazy[2*x+1] += lazy[x];
lazy[2*x+2] += lazy[x];
lazy[x] = 0;
}
}
ll get(int pos , int x , int lx , int rx){
if(rx - lx == 1){
if(set_val[x] != -1){
if(set_val[x] == 0)val[x] = lazy[x];
else val[x] = cap[lx] + lazy[x];
}
else val[x] += lazy[x];
val[x] = max(val[x] , 0LL);
val[x] = min(val[x] , 0LL + cap[lx]);
set_val[x] = -1;
lazy[x] = 0;
return val[x];
}
push(x);
int m = (lx + rx)/2;
if(pos < m)return get(pos , 2 * x + 1 , lx , m);
else return get(pos , 2 * x + 2 , m, rx);
}
ll get(int pos){
return get(pos, 0 , 0 , siz);
}
void set(int l ,int r, ll value , int x , int lx , int rx){
if(lx >= r || l >= rx)return;
if(lx >= l && rx <= r){
set_val[x] = value;
lazy[x] = 0;
return;
}
push(x);
int m = (lx + rx)/2;
set(l , r , value , 2 * x + 1 , lx , m);
set(l ,r , value , 2 * x + 2 , m, rx);
}
void set(int l , int r , ll value){
set(l , r , value , 0 , 0, siz);
}
void add(int l ,int r , ll value , int x , int lx , int rx){
if(lx >= r || l >= rx)return;
if(lx >= l && rx <= r){
lazy[x] += value;
return;
}
push(x);
int m = (lx + rx)/2;
add(l ,r , value , 2 * x + 1 , lx , m);
add(l , r , value , 2 * x + 2 , m , rx);
}
void add(int l , int r , ll value){
add(l , r , value , 0 ,0 ,siz);
}
};
Seg st;
int n;
void query(ll val){
int l = 0 , r = n-1;
int pos = -1;
while(l <= r){
int mid = (l + r)/2;
ll x = st.get(mid);
x = max(x , 0LL);
if(x >= cap[mid])x = cap[mid];
x += val;
if(x <= 0 || x >= cap[mid]){
pos = mid;
l = mid + 1;
}
else r = mid - 1;
}
//cout << "pos " << pos << endl;
if(pos < n-1){
st.add(pos+1 , n , val);
}
if(pos >= 0){
if(val < 0){
st.set(0 , pos + 1 , 0);
}
else st.set(0 , pos + 1 , 1e9);
}
}
vector<int> distribute_candies(vector<int> c, vector<int> l,vector<int> r, vector<int> v){
n = c.size();
cap = c;
vector<int> res(n);
st.init(n + 1);
int q = l.size();
sort(all(cap));
for(int i = 0; i < q; i++){
query(v[i]);
}
for(int i = 0; i < n; i++)res[i] = st.get(i);
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
344 ms |
20412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
