#include "candies.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct node
{
ll m, M, sum;
bool check(int c)
{
return M - m < c;
}
} seg[850005];
node merge(node p, node q)
{
auto [lm, lM, lsum] = p;
auto [rm, rM, rsum] = q;
return node{min(lm + rsum, rm), max(lM + rsum, rM), lsum + rsum};
}
int n, q;
node emp = {0, 0, 0};
void init()
{
for (int i = 1; i <= 4 * (q + 2); i++)
seg[i] = emp;
}
void modify(int pos, node val, int i = 1, int L = 0, int R = q + 1)
{
if (L == R)
seg[i] = val;
else
{
int mid = (L + R) / 2;
if (pos <= mid)
modify(pos, val, i << 1, L, mid);
else
modify(pos, val, i << 1 | 1, mid + 1, R);
seg[i] = merge(seg[i << 1], seg[i << 1 | 1]);
}
}
pair<int, node> search(int c, node suf = emp, int i = 1, int L = 0, int R = q + 1)
{
if (L == R)
return make_pair(L, suf);
else
{
int mid = (L + R) / 2;
if (merge(seg[i << 1 | 1], suf).check(c))
return search(c, merge(seg[i << 1 | 1], suf), i << 1, L, mid);
else
return search(c, suf, i << 1 | 1, mid + 1, R);
}
}
vector<int> in[200000], out[200001];
node base[200002];
vector<int> distribute_candies(vector<int> c, vector<int> l,
vector<int> r, vector<int> v)
{
vector<int> ans;
n = c.size(), q = l.size();
v.insert(v.begin(), -1);
l.insert(l.begin(), 0);
r.insert(r.begin(), 0);
for (int i = 1; i <= q; i++)
{
in[l[i]].emplace_back(i);
out[r[i] + 1].emplace_back(i);
if (v[i] < 0)
base[i] = node{v[i], 0, v[i]};
else
base[i] = node{0, v[i], v[i]};
}
init();
for (int i = 0; i < n; i++)
{
for (auto j : in[i])
modify(j, base[j]);
for (auto j : out[i])
modify(j, emp);
auto [L, s] = search(c[i]);
if (v[L] < 0)
ans.emplace_back(s.M);
else
ans.emplace_back(c[i] + s.m);
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
9684 KB |
Output is correct |
2 |
Correct |
5 ms |
9684 KB |
Output is correct |
3 |
Correct |
7 ms |
10016 KB |
Output is correct |
4 |
Correct |
6 ms |
9940 KB |
Output is correct |
5 |
Correct |
7 ms |
10100 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
351 ms |
48348 KB |
Output is correct |
2 |
Correct |
318 ms |
52800 KB |
Output is correct |
3 |
Correct |
309 ms |
52328 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
175 ms |
43736 KB |
Output is correct |
3 |
Correct |
59 ms |
15876 KB |
Output is correct |
4 |
Correct |
303 ms |
54304 KB |
Output is correct |
5 |
Correct |
314 ms |
54796 KB |
Output is correct |
6 |
Correct |
335 ms |
55132 KB |
Output is correct |
7 |
Correct |
307 ms |
54480 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
9684 KB |
Output is correct |
2 |
Correct |
5 ms |
9704 KB |
Output is correct |
3 |
Correct |
88 ms |
43480 KB |
Output is correct |
4 |
Correct |
52 ms |
12940 KB |
Output is correct |
5 |
Correct |
142 ms |
43388 KB |
Output is correct |
6 |
Correct |
137 ms |
43336 KB |
Output is correct |
7 |
Correct |
135 ms |
43420 KB |
Output is correct |
8 |
Correct |
139 ms |
43544 KB |
Output is correct |
9 |
Correct |
141 ms |
43384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
9684 KB |
Output is correct |
2 |
Correct |
5 ms |
9684 KB |
Output is correct |
3 |
Correct |
7 ms |
10016 KB |
Output is correct |
4 |
Correct |
6 ms |
9940 KB |
Output is correct |
5 |
Correct |
7 ms |
10100 KB |
Output is correct |
6 |
Correct |
351 ms |
48348 KB |
Output is correct |
7 |
Correct |
318 ms |
52800 KB |
Output is correct |
8 |
Correct |
309 ms |
52328 KB |
Output is correct |
9 |
Correct |
5 ms |
9684 KB |
Output is correct |
10 |
Correct |
175 ms |
43736 KB |
Output is correct |
11 |
Correct |
59 ms |
15876 KB |
Output is correct |
12 |
Correct |
303 ms |
54304 KB |
Output is correct |
13 |
Correct |
314 ms |
54796 KB |
Output is correct |
14 |
Correct |
335 ms |
55132 KB |
Output is correct |
15 |
Correct |
307 ms |
54480 KB |
Output is correct |
16 |
Correct |
4 ms |
9684 KB |
Output is correct |
17 |
Correct |
5 ms |
9704 KB |
Output is correct |
18 |
Correct |
88 ms |
43480 KB |
Output is correct |
19 |
Correct |
52 ms |
12940 KB |
Output is correct |
20 |
Correct |
142 ms |
43388 KB |
Output is correct |
21 |
Correct |
137 ms |
43336 KB |
Output is correct |
22 |
Correct |
135 ms |
43420 KB |
Output is correct |
23 |
Correct |
139 ms |
43544 KB |
Output is correct |
24 |
Correct |
141 ms |
43384 KB |
Output is correct |
25 |
Correct |
5 ms |
9708 KB |
Output is correct |
26 |
Correct |
57 ms |
13000 KB |
Output is correct |
27 |
Correct |
182 ms |
43292 KB |
Output is correct |
28 |
Correct |
313 ms |
52920 KB |
Output is correct |
29 |
Correct |
309 ms |
53280 KB |
Output is correct |
30 |
Correct |
297 ms |
53468 KB |
Output is correct |
31 |
Correct |
303 ms |
53732 KB |
Output is correct |
32 |
Correct |
314 ms |
53948 KB |
Output is correct |