#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct SegTree
{
vector<ll> tree, padd, righ, mini, maxi;
void init ( int s )
{
tree = padd = righ = mini = maxi = vector<ll>( 4*s, 0 );
}
void ppush ( int v, int tl, int tr )
{
tree[v] += (tr-tl+1)*padd[v];
righ[v] += padd[v];
mini[v] += padd[v];
maxi[v] += padd[v];
if ( tl != tr )
{
padd[2*v] += padd[v];
padd[2*v+1] += padd[v];
}
padd[v] = 0;
}
void upd ( int v )
{
tree[v] = tree[2*v] + tree[2*v+1];
righ[v] = righ[2*v+1];
mini[v] = min( mini[2*v], mini[2*v+1] );
maxi[v] = max( maxi[2*v], maxi[2*v+1] );
}
void tadd ( int v, int tl, int tr, int l, int r, int x )
{
ppush( v, tl, tr );
if ( tr < l || r < tl )
return;
if ( l <= tl && tr <= r )
{
padd[v] += x;
ppush( v, tl, tr );
return;
}
int mid = ( tl + tr ) / 2;
tadd( 2*v, tl, mid, l, r, x );
tadd( 2*v+1, mid+1, tr, l, r, x );
upd(v);
}
int fnd ( int v, int tl, int tr, int x, ll cmin, ll cmax )
{
ppush( v, tl, tr );
if ( max( maxi[v], cmax ) - min( mini[v], cmin ) <= x )
return tl;
int mid = ( tl + tr ) / 2;
if ( max( maxi[2*v+1], cmax ) - min( mini[2*v+1], cmin ) > x )
return fnd( 2*v+1, mid+1, tr, x, cmin, cmax );
if ( max({ maxi[2*v+1], righ[2*v], cmax }) - min({ mini[2*v+1], righ[2*v], cmin }) <= x )
return fnd( 2*v, tl, mid, x, min( cmin, mini[2*v+1] ), max( cmax, maxi[2*v+1] ) );
return fnd( 2*v+1, mid+1, tr, x, cmin, cmax );
}
ll tget ( int v, int tl, int tr, int pos )
{
ppush( v, tl, tr );
if ( tl == tr )
return tree[v];
int mid = ( tl + tr ) / 2;
if ( pos <= mid )
return tget( 2*v, tl, mid, pos );
return tget( 2*v+1, mid+1, tr, pos );
}
ll tfnc ( int v, int tl, int tr, int l, int r, bool bmin )
{
ppush( v, tl, tr );
if ( tr < l || r < tl )
return bmin ? 1e18 : -1e18;
if ( l <= tl && tr <= r )
return bmin ? mini[v] : maxi[v];
int mid = ( tl + tr ) / 2;
if ( bmin )
return min( tfnc( 2*v, tl, mid, l, r, true ), tfnc( 2*v+1, mid+1, tr, l, r, true ) );
return max( tfnc( 2*v, tl, mid, l, r, false ), tfnc( 2*v+1, mid+1, tr, l, r, false ) );
}
}
stree;
vector<int> distribute_candies( vector<int> c, vector<int> l, vector<int> r, vector<int> v )
{
int n = c.size();
int m = v.size();
vector< vector< pair<int,int> > > event( n+1 );
for ( int i=0; i<m; i++ )
{
event[ l[i] ].push_back({ i+1, v[i] });
event[ r[i]+1 ].push_back({ i+1, -v[i] });
}
stree.init(m+1);
vector<int> ans(n);
for ( int i=0; i<n; i++ )
{
for ( auto& [ind,delt] : event[i] )
stree.tadd( 1, 0, m, ind, m, delt );
int p = stree.fnd( 1, 0, m, c[i], 1e18, -1e18 );
ll endval = stree.tget( 1, 0, m, m );
if ( p == 0 )
ans[i] = endval;
else
{
ll x = stree.tget( 1, 0, m, p-1 );
ll mini = stree.tfnc( 1, 0, m, p, m, true );
ll maxi = stree.tfnc( 1, 0, m, p, m, false );
if ( x < mini )
ans[i] = endval - ( maxi - c[i] );
else
ans[i] = endval - mini;
}
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
172 ms |
106784 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
296 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
193 ms |
42380 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
