#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()
typedef long long ll;
const ll maxn = 200010;
const ll mod = 1000000007;
const ll inf = mod * mod;
ll cap[maxn], N;
struct node{
ll mn, mx, lazysum, set0, setmx;
node(ll val){
mn = val;
mx = val;
lazysum = 0;
set0 = -1;
setmx = -1;
}
node(){
mn = mod;
mx = -mod;
lazysum = 0;
set0 = -1;
setmx = -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(ll nod,ll l,ll r){
if( st[nod].set0 != -1 ){
st[nod].mn = 0;
st[nod].mx = 0;
if( l != r ){
st[2*nod].set0 = 1;
st[2*nod].lazysum = 0;
st[2*nod].setmx = -1;
st[2*nod+1].set0 = 1;
st[2*nod+1].lazysum = 0;
st[2*nod+1].setmx = -1;
}
st[nod].set0 = -1;
}
if( st[nod].setmx != -1 ){
st[nod].mn = cap[l];
st[nod].mx = cap[r];
if( l != r ){
st[2*nod].setmx = 1;
st[2*nod].lazysum = 0;
st[2*nod].set0 = -1;
st[2*nod+1].setmx = 1;
st[2*nod+1].lazysum = 0;
st[2*nod+1].set0 = -1;
}
st[nod].setmx = -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_(ll nod,ll l,ll r,ll x,ll y,ll 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;
}
ll 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 ){
if( val == 0 ) st[nod].set0 = 1, st[nod].setmx = -1;
if( val == 1 ) st[nod].setmx = 1, st[nod].set0 = -1;
st[nod].lazysum = 0;
lazyp(nod,l,r);
return;
}
ll 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];
ll mi = ( l + r ) >> 1;
return merge_( get_(2*nod,l,mi,x,y) , get_(2*nod+1,mi+1,r,x,y) );
}
//void chapeo(ll nod,ll l,ll 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;
// ll mi = ( l + r ) >> 1;
// chapeo(2*nod,l,mi);
// chapeo(2*nod+1,mi+1,r);
//}
//int get_fst_mn(ll nod,ll l,ll r){
// lazyp(nod,l,r);
// if( l == r ){
// if( st[nod].mn < 0 ) return l;
// else return N;
// }
// ll 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) {
ll n = c.size();
N = n;
ll q = l.size();
vector<pair<int,int>> a(n);
for(int i=0; i<n; i++){
a[i] = { c[i] , i };
}
sort(all(a));
for(int i=0; i<n; i++)
cap[i] = a[i].f;
build();
for(int i=0; i<q; i++){
//sum_(1,0,n-1,l[i],r[i],v[i]);
if( v[i] > 0 ){
int l = 0, r = n - 1;
if( get_(1,0,n-1,0,0).mn + v[i] <= cap[0] ){
sum_(1,0,n-1,0,n-1,v[i]);
continue;
}
if( get_(1,0,n-1,n-1,n-1).mn + v[i] > cap[n-1] ){
set_(1,0,n-1,0,n-1,1);
continue;
}
while( l < r ){
int mi = ( l + r ) >> 1;
ll u = get_(1,0,n-1,mi,mi).mn;
if( u + v[i] <= cap[mi] ) r = mi;
else l = mi + 1;
}
//db(get_(1,0,n-1,l,l).mn+v[i])db(cap[l])
set_(1,0,n-1,0,l-1,1);
sum_(1,0,n-1,l,n-1,v[i]);
}
if( v[i] < 0 ){
int l = 0, r = n - 1;
if( get_(1,0,n-1,0,0).mn + v[i] >= 0 ){
sum_(1,0,n-1,0,n-1,v[i]);
continue;
}
if( get_(1,0,n-1,n-1,n-1).mn + v[i] < 0 ){
set_(1,0,n-1,0,n-1,0);
continue;
}
while( l < r ){
int mi = ( l + r ) >> 1;
ll u = get_(1,0,n-1,mi,mi).mn;
if( u + v[i] >= 0 ) r = mi;
else l = mi + 1;
}
//db(get_(1,0,n-1,l,l).mn+v[i])db(cap[l])
set_(1,0,n-1,0,l-1,0);
sum_(1,0,n-1,l,n-1,v[i]);
}
}
std::vector<int> ans(n);
for(int i=0; i<n; i++)
ans[a[i].s] = get_(1,0,n-1,i,i).mn;
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
31564 KB |
Output is correct |
| 2 |
Incorrect |
18 ms |
31564 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
603 ms |
41784 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
31564 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
31616 KB |
Output is correct |
| 2 |
Correct |
19 ms |
31548 KB |
Output is correct |
| 3 |
Correct |
787 ms |
36360 KB |
Output is correct |
| 4 |
Correct |
196 ms |
37132 KB |
Output is correct |
| 5 |
Correct |
2220 ms |
41776 KB |
Output is correct |
| 6 |
Correct |
2262 ms |
41776 KB |
Output is correct |
| 7 |
Correct |
2170 ms |
41776 KB |
Output is correct |
| 8 |
Correct |
2188 ms |
41784 KB |
Output is correct |
| 9 |
Correct |
289 ms |
41740 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
31564 KB |
Output is correct |
| 2 |
Incorrect |
18 ms |
31564 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
