#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, QQ, Q;
int A[MAXN+10];
Query BB[MAXN+10], B[MAXN+10];
int ans[MAXN+10];
ll P[MAXN+10];
ll T[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++) BB[i]={_L[i-1], _R[i-1], _V[i-1]};
QQ=1;
for(int i=1; i<=Q; i++)
{
if(i==1 || (B[QQ].v>0 && BB[i].v>0) || (B[QQ].v<0 && BB[i].v<0)) B[QQ].v+=BB[i].v;
else B[++QQ].v=BB[i].v;
}
Q=QQ;
if(Q==1)
{
if(B[1].v>0)
{
for(int i=1; i<=N; i++) ans[i]=min(A[i], B[1].v);
}
return vector<int>(ans+1, ans+N+1);
}
for(int i=Q; i>=1; i--) P[i]=P[i+1]+B[i].v;
for(int i=1; i<=Q; i++) T[i]=INF;
ll p=0, q=0;
for(int i=Q; i>=1; i--)
{
if(B[i].v>0)
{
if(P[i]>=p)
{
T[i]=max(0ll, P[i]-q);
}
p=max(p, P[i]);
}
else if(B[i].v<0)
{
if(P[i]<=q)
{
T[i]=max(0ll, p-P[i]);
}
q=min(q, P[i]);
}
}
vector<pll> V, V2, V3;
for(int i=1; i<=Q; i++) V.push_back({T[i], i});
sort(V.begin(), V.end());
for(int i=1; i<=N; i++) V2.push_back({A[i], i});
sort(V2.begin(), V2.end());
//for(int i=1; i<=Q; i++) printf("%lld ", T[i]); printf("\n");
ll t=0, t2=0;
for(int i=1; i<=Q; i++)
{
t+=B[i].v;
t=max(t, 0ll);
t2=max(t2, t);
V3.push_back({t2, i});
}
V3.push_back({t2, Q+1});
int meet=0;
priority_queue<int, vector<int>, greater<int>> PQ1, PQ2;
for(int i=0, j=0, k=0; i<V2.size(); i++)
{
for(; k<V3.size() && V3[k].first<V2[i].first; k++)
{
meet=max(meet, (int)V3[k].second);
if(V3[k].first>=V2[i].first) break;
}
for(; j<V.size() && V[j].first<=V2[i].first; j++)
{
if(B[V[j].second].v>0) PQ1.push(V[j].second);
else PQ2.push(V[j].second);
}
while(!PQ2.empty() && PQ2.top()<meet) PQ2.pop();
int pos=Q+1;
if(!PQ1.empty()) pos=min(pos, PQ1.top());
if(!PQ2.empty()) pos=min(pos, PQ2.top());
//printf("%d -> %d %d\n", V2[i].second, pos, meet);
if(pos==Q+1) ans[V2[i].second]=0;
else if(B[pos].v>=0) ans[V2[i].second]=P[pos];
else ans[V2[i].second]=V2[i].first+P[pos];
}
return vector<int>(ans+1, ans+N+1);
}
Compilation message
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:94:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | for(int i=0, j=0, k=0; i<V2.size(); i++)
| ~^~~~~~~~~~
candies.cpp:96:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for(; k<V3.size() && V3[k].first<V2[i].first; k++)
| ~^~~~~~~~~~
candies.cpp:101:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | for(; j<V.size() && V[j].first<=V2[i].first; j++)
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
147 ms |
16148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
