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 "candies.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int nt = 1;
vector<ll> st_mx, st_mn;
ll get_range_mx(int l, int r, int k, int x, int y)
{
if (y < l || x > r) return 0;
if (x >= l && y <= r) return st_mx[k];
int c = (x + y) / 2;
return max(get_range_mx(l, r, k*2, x, c), get_range_mx(l, r, k*2|1, c+1, y));
}
ll get_range_mn(int l, int r, int k, int x, int y)
{
if (y < l || x > r) return 1ll << 60;
if (x >= l && y <= r) return st_mn[k];
int c = (x + y) / 2;
return min(get_range_mn(l, r, k*2, x, c), get_range_mn(l, r, k*2|1, c+1, y));
}
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v)
{
int N = c.size();
int Q = l.size();
vector<pair<ll, int>> box(N);
for (int i = 0; i < N; i++)
box[i] = {c[i], i};
sort(box.begin(), box.end());
reverse(box.begin(), box.end());
while (nt <= Q) nt <<= 1;
st_mx = vector<ll>(nt * 2);
st_mn = vector<ll>(nt * 2, 1ll << 60);
ll sum = 0;
map<ll, int> ps_pos;
for (int i = 0; i < Q; i++)
{
sum += v[i];
st_mx[i + nt + 1] = sum;
st_mn[i + nt + 1] = sum;
ps_pos[sum] = i + 1;
}
st_mn = st_mx; for (int i = nt - 1; i >= 1; i--)
st_mx[i] = max(st_mx[i*2], st_mx[i*2|1]);
for (int i = nt - 1; i >= 1; i--)
st_mn[i] = min(st_mn[i*2], st_mn[i*2|1]);
int time = 0; int score = 0;
bool minimized = true;
for (int i = 0; i < Q; i++)
{
score += v[i];
if (score <= 0)
{
time = i + 1;
score = 0;
minimized = true;
}
else if (score >= box[0].first)
{
time = i + 1;
score = box[0].first;
minimized = false;
}
}
vector<int> res(N);
res[box[0].second] = score;
for (int i = 1; i < N; i++)
{
if (minimized)
{
ll mx = get_range_mx(time, Q, 1, 0, nt - 1);
if (mx - st_mx[nt + time] >= (ll)box[i].first)
{
time = ps_pos[mx];
minimized = false;
}
}
else
{
ll mn = get_range_mn(time, Q, 1, 0, nt - 1);
if (box[i].first - (st_mn[nt + time] - mn) <= 0ll)
{
time = ps_pos[mn];
minimized = true;
}
}
//cerr << st_mx[nt + Q] << " - " << st_mx[nt + time] << '\n';
res[box[i].second] = st_mx[nt + Q] - st_mx[nt + time];
if (!minimized)
res[box[i].second] += box[i].first;
}
return res;
}
# | 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... |