#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline","03")
#define f first
#define s second
#define db(x) cerr << #x << ": " << (x) << '\n';
#define pb push_back
#define all(x) x.begin() , x.end()
const int maxn = 200010;
const int mod = 1000000007;
const int inf = 1000000007;
int cap, N;
struct node{
int mn, mx, lazysum, lazyset;
node(int val){
mn = val;
mx = val;
lazysum = 0;
lazyset = -1;
}
node(){
mn = mod;
mx = -mod;
lazysum = 0;
lazyset = -1;
}
} st[maxn*4];
void build(){
for(int i=0; i<maxn*4; i++)
st[i] = node(0);
}
node merge_(node a,node b){
node c = node();
c.mn = min( a.mn , b.mn );
c.mx = max( a.mx , b.mx );
return c;
}
void lazyp(int nod,int l,int r){
if( st[nod].lazyset != -1 ){
st[nod].mn = st[nod].lazyset;
st[nod].mx = st[nod].lazyset;
if( l != r ){
st[2*nod].lazyset = st[nod].lazyset;
st[2*nod].lazysum = 0;
st[2*nod+1].lazyset = st[nod].lazyset;
st[2*nod+1].lazysum = 0;
}
st[nod].lazyset = -1;
}
st[nod].mn += st[nod].lazysum;
st[nod].mx += st[nod].lazysum;
if( l != r ){
st[2*nod].lazysum += st[nod].lazysum;
st[2*nod+1].lazysum += st[nod].lazysum;
}
st[nod].lazysum = 0;
}
void sum_(int nod,int l,int r,int x,int y,int val){
lazyp(nod,l,r);
if( l > y || r < x ) return;
if( l >= x && r <= y ){
st[nod].lazysum += val;
lazyp(nod,l,r);
return;
}
int mi = ( l + r ) >> 1;
sum_(2*nod,l,mi,x,y,val);
sum_(2*nod+1,mi+1,r,x,y,val);
st[nod] = merge_( st[2*nod] , st[2*nod+1] );
}
void set_(int nod,int l,int r,int x,int y,int val){
lazyp(nod,l,r);
if( l > y || r < x ) return;
if( l >= x && r <= y ){
st[nod].lazyset = val;
st[nod].lazysum = 0;
lazyp(nod,l,r);
return;
}
int mi = ( l + r ) >> 1;
set_(2*nod,l,mi,x,y,val);
set_(2*nod+1,mi+1,r,x,y,val);
st[nod] = merge_( st[2*nod] , st[2*nod+1] );
}
node get_(int nod,int l,int r,int x,int y){
lazyp(nod,l,r);
if( l > y || r < x ) return node();
if( l >= x && r <= y ) return st[nod];
int mi = ( l + r ) >> 1;
return merge_( get_(2*nod,l,mi,x,y) , get_(2*nod+1,mi+1,r,x,y) );
}
void chapeo(int nod,int l,int r){
lazyp(nod,l,r);
if( st[nod].mx < 0 ){
st[nod].lazyset = 0;
st[nod].lazysum = 0;
lazyp(nod,l,r);
return;
}
if( st[nod].mn > cap ){
st[nod].lazyset = cap;
st[nod].lazysum = 0;
lazyp(nod,l,r);
return;
}
if( st[nod].mn >= 0 && st[nod].mx <= cap )
return;
int mi = ( l + r ) >> 1;
chapeo(2*nod,l,mi);
chapeo(2*nod+1,mi+1,r);
}
int get_fst_mn(int nod,int l,int r){
lazyp(nod,l,r);
if( l == r ){
if( st[nod].mn < 0 ) return l;
else return N;
}
int mi = ( l + r ) >> 1;
lazyp(2*nod,l,mi);
if( st[2*nod].mn < 0 ) return get_fst_mn(2*nod,l,mi);
lazyp(2*nod+1,mi+1,r);
if( st[2*nod+1].mn < 0 ) return get_fst_mn(2*nod+1,mi+1,r);
return N;
}
int get_fst_mx(int nod,int l,int r){
lazyp(nod,l,r);
if( l == r ){
if( st[nod].mx > cap ) return l;
else return N;
}
int mi = ( l + r ) >> 1;
lazyp(2*nod,l,mi);
if( st[2*nod].mx > cap ) return get_fst_mx(2*nod,l,mi);
lazyp(2*nod+1,mi+1,r);
if( st[2*nod+1].mx > cap ) return get_fst_mx(2*nod+1,mi+1,r);
return N;
}
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v) {
int n = c.size();
N = n;
int q = l.size();
cap = c[0];
build();
for(int i=0; i<q; i++){
sum_(1,0,n-1,l[i],r[i],v[i]);
chapeo(1,0,n-1);
}
std::vector<int> ans(n);
for(int i=0; i<n; i++)
ans[i] = get_(1,0,n-1,i,i).mn;
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
12748 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
12748 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1136 ms |
19880 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
12748 KB |
Output is correct |
| 2 |
Incorrect |
180 ms |
17480 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
12748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
12748 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
12748 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
