#include "candies.h"
#include <vector>
#include <algorithm>
#include <utility>
#include <cstdio>
#define ll long long
using namespace std;
#define BLKSIZE 500
int n, q;
int c[200005];
int l[200005], r[200005];
int v[200005];
int ans[200005];
// amount from empty vs. cap
vector<pair<int, int> > funcs[200005];
vector<int> funcpsum[200005];
ll reclow[200005], rechigh[200005];
void work(int from, int to)
{
//fprintf(stderr, "%d %d\n", from, to);
vector<int> usefuncs;
int curfunc = 0; funcs[0].clear();
reclow[0] = rechigh[0] = 0;
ll curv = 0;
for (int i = 1; i <= q; i++) {
if (r[i] < from || l[i] > to) continue;
if (l[i] <= from && to <= r[i]) {
curv += v[i];
reclow[curfunc] = min(reclow[curfunc], curv);
rechigh[curfunc] = max(rechigh[curfunc], curv);
int base_value = 0;
if (v[i] > 0) {
//int curback = 0;
while (!funcs[curfunc].empty() && funcs[curfunc].back().first - base_value <= v[i]) {
base_value += funcs[curfunc].back().second - funcs[curfunc].back().first;
//curback = funcs[curfunc].back().second;
funcs[curfunc].pop_back();
}
funcs[curfunc].push_back(make_pair(0, v[i] + base_value));
} else {
while (!funcs[curfunc].empty() && funcs[curfunc].back().second - funcs[curfunc].back().first + base_value <= -v[i]) {
base_value += funcs[curfunc].back().second - funcs[curfunc].back().first;
funcs[curfunc].pop_back();
}
if (!funcs[curfunc].empty()) {
funcs[curfunc][funcs[curfunc].size() - 1].first += -v[i] - base_value;
}
}
/*for (int x = 0; x <= curfunc; x++) {
fprintf(stderr, "func %d: ", x);
for (int j = 0; j < funcs[x].size(); j++) {
fprintf(stderr, "(%d, %d) ", funcs[x][j].first, funcs[x][j].second);
}
}*/
} else {
usefuncs.push_back(curfunc);
usefuncs.push_back(-i);
curfunc++; funcs[curfunc].clear();
reclow[curfunc] = rechigh[curfunc] = 0;
curv = 0;
}
}
usefuncs.push_back(curfunc);
for (int i = 0; i <= curfunc; i++) {
//fprintf(stderr, "func %d: ", i);
funcpsum[i].resize(funcs[i].size()); // ?
int cursum = 0;
for (int j = 0; j < funcs[i].size(); j++) {
//fprintf(stderr, "(%d, %d) ", funcs[i][j].first, funcs[i][j].second);
cursum += funcs[i][j].second - funcs[i][j].first;
funcpsum[i][j] = cursum;
}
//fprintf(stderr, "\n");
}
for (int i = from; i <= to; i++) {
for (int j = 0; j < usefuncs.size(); j++) {
if (usefuncs[j] < 0) {
int opid = -usefuncs[j];
if (l[opid] <= i && i <= r[opid]) {
ans[i] += v[opid];
if (ans[i] < 0) ans[i] = 0;
if (ans[i] > c[i]) ans[i] = c[i];
}
} else {
int fid = usefuncs[j];
int funcval;
if (funcs[fid].empty() || c[i] <= funcs[fid][0].first) {
funcval = 0;
} else {
int L = 0; int R = (int)(funcs[fid].size()) - 1;
while (L < R) {
int mid = (L + R) / 2 + 1;
if (funcs[fid][mid].first <= c[i]) {
L = mid;
} else {
R = mid - 1;
}
}
if (funcs[fid][L].second <= c[i]) {
funcval = funcpsum[fid][L];
} else {
funcval = funcpsum[fid][L] - (funcs[fid][L].second - c[i]);
}
}
ll switchval_low = -reclow[fid];
ll switchval_high = (ll)c[i] - rechigh[fid];
if (switchval_high < switchval_low || ans[i] < switchval_low) {
ans[i] = funcval;
} else {
ans[i] = (ll)funcval - switchval_low + min((ll)ans[i], switchval_high);
}
}
}
}
}
vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> V)
{
n = (int)C.size(); q = (int)L.size();
for (int i = 1; i <= n; i++) {
c[i] = C[i-1];
}
for (int i = 1; i <= q; i++) {
l[i] = L[i-1] + 1;
r[i] = R[i-1] + 1;
v[i] = V[i-1];
}
for (int i = 1; i <= n; i += BLKSIZE) {
work(i, min(i + BLKSIZE - 1, n));
}
vector<int> ansvec(n);
for (int i = 0; i < n; i++) ansvec[i] = ans[i+1];
return ansvec;
}
Compilation message
candies.cpp: In function 'void work(int, int)':
candies.cpp:75:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for (int j = 0; j < funcs[i].size(); j++) {
| ~~^~~~~~~~~~~~~~~~~
candies.cpp:83:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | for (int j = 0; j < usefuncs.size(); j++) {
| ~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3937 ms |
20984 KB |
Output is correct |
| 2 |
Correct |
4096 ms |
23388 KB |
Output is correct |
| 3 |
Correct |
4002 ms |
23436 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
9676 KB |
Output is correct |
| 2 |
Correct |
2286 ms |
21984 KB |
Output is correct |
| 3 |
Incorrect |
93 ms |
14728 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
9676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
