This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int MAXQ = 1000005;
const ll INF = (ll)(1e18);
vector<int> distribute_candies(vector<int> c, vector<int> L, vector<int> R, vector<int> v)
{
int n = c.size(); int q = v.size();
vector<ll> p;
p.push_back(INF); p.push_back(0LL);
for(int i=0;i<q;i++) p.push_back(p.back() + v[i]);
q+=2;
vector<ll> smax(q),smin(q);
smax[q-1] = smin[q-1] = p[q-1];
for(int i=q-2;i>=0;i--)
{
smax[i] = max(smax[i+1],p[i]);
smin[i] = min(smin[i+1],p[i]);
}
vector<int> final_A(n);
for(int i=0;i<n;i++)
{
int l = 0; int r = q-1;
int ret = -1;
while(l<=r)
{
int mid = (l+r)/2;
if(smax[mid]-smin[mid]>=c[i])
{
ret = mid;
l = mid+1;
}
else r = mid-1;
}
if(p[ret]==smax[ret]) final_A[i] = p[q-1]-smin[ret];
else final_A[i] = c[i]-(smax[ret]-p[q-1]);
}
return final_A;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |