#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
const int mxN = 2e5 + 7;
const int SZ = exp2(ceil(log2(mxN)));
pair<pair<int,int>,int> seg[5 * mxN];
int lazy[5 * mxN], n, q, len;
void push(int ind, int l, int r, int cnt = 1) {
seg[ind].f.f += lazy[ind], seg[ind].f.s += lazy[ind];
if (l != r) {
lazy[2 * ind] += lazy[ind];
lazy[2 * ind + 1] += lazy[ind];
if (cnt) {
int mid = (l + r) / 2;
push(2 * ind, l, mid, cnt - 1);
push(2 * ind + 1, mid + 1, r, cnt - 1);
}
}
lazy[ind] = 0;
}
void update(int lo, int hi, int val, int ind = 1, int l = 0, int r = SZ - 1) {
push(ind, l, r);
if (lo > r || l > hi) {
return;
}
if (lo <= l && r <= hi) {
push(ind, l, r);
lazy[ind] += val;
if (l == r) {
seg[ind].s = l;
}
push(ind, l, r);
return;
}
int mid = (l + r) / 2;
update(lo, hi, val, 2 * ind, l, mid);
push(ind, l, r);
update(lo, hi, val, 2 * ind + 1, mid + 1, r);
push(ind, l, r);
seg[ind].f.f = min(seg[2 * ind].f.f, seg[2 * ind + 1].f.f);
seg[ind].f.s = max(seg[2 * ind].f.s, seg[2 * ind + 1].f.s);
push(ind, l, r);
}
int query(int pos, int ind = 1, int l = 0, int r = SZ - 1) {
push(ind, l, r);
if (l == r) {
return seg[ind].f.f;
}
int mid = (l + r) / 2;
if (pos <= mid) {
return query(pos, 2 * ind, l, mid);
}
else {
return query(pos, 2 * ind + 1, mid + 1, r);
}
}
int walk(int lo, int val, bool t, int ind = 1, int l = 0, int r = SZ - 1) {
push(ind, l, r);
if (lo > r || (t && seg[ind].f.s <= val) || (!t && seg[ind].f.f >= val)) {
return (t ? INT_MIN : INT_MAX);
}
if (l == r) {
if (t) {
update(l, len, -seg[ind].f.s + val);
}
else {
update(l, len, -seg[ind].f.f);
}
push(ind, l, r);
return seg[ind].s;
}
int mid = (l + r) / 2;
if (l >= lo) {
push(ind, l, r);
if ((t && seg[2*ind].f.s > val) || (!t && seg[2*ind].f.f < val)) {
return walk(lo, val, t, 2 * ind, l, mid);
}
else {
return walk(lo, val, t, 2 * ind + 1, mid + 1, r);
}
}
push(ind, l, r);
int res = walk(lo, val, t, 2 * ind, l, mid);
push(ind, l, r);
if (res == INT_MIN || res == INT_MAX) {
res = walk(lo, val, t, 2 * ind + 1, mid + 1, r);
push(ind, l, r);
}
return res;
}
vector<int> distribute_candies(vector<int> c, vector<int> l,
vector<int> r, vector<int> v) {
n = c.size(), q = v.size();
bool sbt2 = true;
for (int i = 0; i < q; ++i) {
if (v[i] <= 0) {
sbt2 = false;
}
}
vector<int> ans(n);
if (n <= 2000 && q <= 2000) {
for (int i = 0; i < q; ++i) {
for (int j = l[i]; j <= r[i]; ++j) {
ans[j] += v[i];
ans[j] = max(ans[j], 0);
ans[j] = min(ans[j], c[j]);
}
}
}
else if (sbt2) {
vector<long long> pref(n + 1);
for (int i = 0; i < q; ++i) {
pref[r[i] + 1] -= v[i];
pref[l[i]] += v[i];
}
for (int i = 0; i < n; ++i) {
if (i) {
pref[i] += pref[i - 1];
}
ans[i] = min((long long) c[i], pref[i]);
}
}
else {
int cur = 0;
vector<int> calc;
for (int i = 0; i < q; ++i) {
cur += v[i];
calc.push_back(cur);
if (cur <= 0) {
cur = 0;
calc.clear();
}
}
len = calc.size();
for (int i = 0; i < calc.size(); ++i) {
update(i + 1, i + 1, calc[i]);
}
vector<pair<int,int>> arr;
for (int i = 0; i < n; ++i) {
arr.push_back({c[i], i});
}
sort(arr.begin(), arr.end(), greater<pair<int,int>>());
int ind = 1;
for (int i = 0; i < n; ++i) {
while (walk(ind, arr[i].f, 1) != INT_MIN) {
int nex = walk(ind, 0, 0);
if (nex != INT_MAX) {
ind = nex + 1;
}
}
ans[arr[i].s] = query(len);
}
}
return ans;
}
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:160:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
160 | for (int i = 0; i < calc.size(); ++i) {
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
3 ms |
380 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
82 ms |
8816 KB |
Output is correct |
| 2 |
Correct |
78 ms |
12912 KB |
Output is correct |
| 3 |
Correct |
82 ms |
12728 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
273 ms |
12260 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
60 ms |
5796 KB |
Output is correct |
| 4 |
Correct |
284 ms |
4928 KB |
Output is correct |
| 5 |
Correct |
532 ms |
16512 KB |
Output is correct |
| 6 |
Correct |
414 ms |
12172 KB |
Output is correct |
| 7 |
Correct |
518 ms |
9664 KB |
Output is correct |
| 8 |
Correct |
476 ms |
15584 KB |
Output is correct |
| 9 |
Correct |
79 ms |
8908 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
3 ms |
380 KB |
Output is correct |
| 6 |
Correct |
82 ms |
8816 KB |
Output is correct |
| 7 |
Correct |
78 ms |
12912 KB |
Output is correct |
| 8 |
Correct |
82 ms |
12728 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Incorrect |
273 ms |
12260 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
