#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 2e5;
const ll INF = 1e18;
struct Query
{
int l, r, v;
};
int N, Q;
int A[MAXN+10];
Query B[MAXN+10];
int ans[MAXN+10];
struct Node
{
ll val, maxv, minv;
Node() : val(0), maxv(0), minv(0) {}
};
Node operator + (const Node &p, const Node &q)
{
Node ret;
ret.maxv=max(p.maxv, q.maxv);
ret.minv=min(p.minv, q.minv);
ret.val=max({p.val, q.val, p.maxv-q.minv, q.maxv-p.minv});
return ret;
}
struct SEG
{
Node tree[MAXN*4+10];
ll lazy[MAXN*4+10];
void busy(int node, int tl, int tr)
{
if(lazy[node]==0) return;
tree[node].maxv+=lazy[node];
tree[node].minv+=lazy[node];
if(tl!=tr)
{
lazy[node*2]+=lazy[node];
lazy[node*2+1]+=lazy[node];
}
lazy[node]=0;
return;
}
void update(int node, int tl, int tr, int l, int r, ll k)
{
busy(node, tl, tr);
if(l<=tl && tr<=r)
{
lazy[node]+=k;
busy(node, tl, tr);
return;
}
if(r<tl || tr<l) return;
int mid=tl+tr>>1;
update(node*2, tl, mid, l, r, k);
update(node*2+1, mid+1, tr, l, r, k);
tree[node]=tree[node*2]+tree[node*2+1];
}
int query(int node, int tl, int tr, ll k, Node p)
{
if(tl==tr)
{
Node t;
if(p.val<0) t=tree[node];
else t=p+tree[node];
if(t.val<=k) return tl;
return tl+1;
}
int mid=tl+tr>>1;
busy(node, tl, tr);
busy(node*2, tl, mid);
busy(node*2+1, mid+1, tr);
Node t;
if(p.val<0) t=tree[node*2+1];
else t=tree[node*2+1]+p;
if(t.val<=k) return query(node*2, tl, mid, k, t);
else return query(node*2+1, mid+1, tr, k, p);
}
ll get(int node, int tl, int tr, int p)
{
busy(node, tl, tr);
if(tl==tr) return tree[node].minv;
int mid=tl+tr>>1;
if(p<=mid) return get(node*2, tl, mid, p);
else return get(node*2+1, mid+1, tr, p);
}
}seg;
ll S[MAXN+10], P[MAXN+10];
vector<int> distribute_candies(vector<int> _C, vector<int> _L, vector<int> _R, vector<int> _V)
{
N=_C.size(); Q=_L.size();
for(int i=1; i<=N; i++) A[i]=_C[i-1];
for(int i=1; i<=Q; i++) B[i]={_L[i-1]+1, _R[i-1]+1, _V[i-1]};
vector<pii> V;
for(int i=1; i<=Q; i++)
{
V.push_back({B[i].l, i});
V.push_back({B[i].r+1, -i});
}
sort(V.begin(), V.end());
ll sum=0;
for(int i=1, j=0; i<=N; i++)
{
for(; j<V.size() && V[j].first<=i; j++)
{
int t=V[j].second;
if(t>0)
{
for(int k=t; k<=Q; k++) S[k]+=B[t].v;
sum+=B[t].v;
}
else
{
for(int k=-t; k<=Q; k++) S[k]+=-B[-t].v;
sum+=-B[-t].v;
}
}
ll minv=sum, maxv=sum;
for(int k=Q; k>=0; k--)
{
minv=min(minv, S[k]);
maxv=max(maxv, S[k]);
if(maxv-minv>A[i])
{
if(S[k]==maxv) ans[i]=sum-minv;
else if(S[k]==minv) ans[i]=A[i]-(maxv-sum);
break;
}
}
//printf("%d ==> %d\n", i, ans[i]);
}
return vector<int>(ans+1, ans+N+1);
sum=0;
for(int i=1, j=0; i<=N; i++)
{
for(; j<V.size() && V[j].first<=i; j++)
{
int t=V[j].second;
if(t>0)
{
seg.update(1, 0, Q, t, Q, B[t].v);
sum+=B[t].v;
}
else
{
seg.update(1, 0, Q, -t, Q, -B[-t].v);
sum+=-B[-t].v;
}
}
Node t;
t.val=-1;
int pos=seg.query(1, 0, Q, A[i], t);
printf("%d\n", pos);
}
return vector<int>(ans+1, ans+N+1);
}
Compilation message
candies.cpp: In member function 'void SEG::update(int, int, int, int, int, ll)':
candies.cpp:66:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
66 | int mid=tl+tr>>1;
| ~~^~~
candies.cpp: In member function 'int SEG::query(int, int, int, ll, Node)':
candies.cpp:82:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
82 | int mid=tl+tr>>1;
| ~~^~~
candies.cpp: In member function 'll SEG::get(int, int, int, int)':
candies.cpp:97:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
97 | int mid=tl+tr>>1;
| ~~^~~
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:122:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | for(; j<V.size() && V[j].first<=i; j++)
| ~^~~~~~~~~
candies.cpp:155:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
155 | for(; j<V.size() && V[j].first<=i; j++)
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
19020 KB |
Output is correct |
| 2 |
Correct |
9 ms |
19008 KB |
Output is correct |
| 3 |
Incorrect |
12 ms |
19276 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5087 ms |
33480 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
19020 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
19072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
19020 KB |
Output is correct |
| 2 |
Correct |
9 ms |
19008 KB |
Output is correct |
| 3 |
Incorrect |
12 ms |
19276 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
