#include "candies.h"
#include <vector>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;
// segment tree with both min and max storage
// min stores the minimum number of candies that are in the box at any time
// max stores the maximum number of candies that are in the box at any time
// the nth node in the underlying array of the segment tree stores the state of the box
// after the nth update has been processed.
// we process the updates in order of ranges rather than chronilogical order, allowing the
// final value for each box to be determined one by one from left to right
vector<int> segment_tree_sum;
vector<int> segment_tree_min;
vector<int> segment_tree_max;
vector<int> lazy;
void push_lazy(int i);
void add(int sl, int sr, int l, int r, int v, int i = 1) {
// cout << sl << " => " << sr << " " << l << " => " << r << " " << v << "\n";
if (sl != sr) {
// lazy[i] += v;
push_lazy(i);
}
if (sl == l && sr == r) {
if (sl != sr) {
lazy[i] += v;
push_lazy(i);
}
else {
segment_tree_sum[i] += v;
segment_tree_min[i] += v;
segment_tree_max[i] += v;
}
return;
}
int mid = (sl + sr) / 2;
if (l <= mid) {
add(sl, mid, l, min(r, mid), v, i*2);
}
if (r > mid) {
add(mid+1, sr, max(l, mid+1), r, v, i*2+1);
}
segment_tree_min[i] = min(segment_tree_min[i*2], segment_tree_min[i*2+1]);
segment_tree_max[i] = max(segment_tree_max[i*2], segment_tree_max[i*2+1]);
segment_tree_sum[i] = segment_tree_sum[i*2] + segment_tree_sum[i*2+1];
}
void push_lazy(int i) {
if (i*2 >= (int) segment_tree_sum.size()) return;
if (lazy[i] == 0) {
segment_tree_min[i] = min(segment_tree_min[i*2], segment_tree_min[i*2+1]);
segment_tree_max[i] = max(segment_tree_max[i*2], segment_tree_max[i*2+1]);
return;
}
lazy[i*2] += lazy[i];
lazy[i*2+1] += lazy[i];
segment_tree_sum[i*2] += lazy[i];
segment_tree_sum[i*2+1] += lazy[i];
segment_tree_min[i*2] += lazy[i];
segment_tree_min[i*2+1] += lazy[i];
segment_tree_max[i*2] += lazy[i];
segment_tree_max[i*2+1] += lazy[i];
lazy[i] = 0;
segment_tree_min[i] = min(segment_tree_min[i*2], segment_tree_min[i*2+1]);
segment_tree_max[i] = max(segment_tree_max[i*2], segment_tree_max[i*2+1]);
}
vector<int> query(int sl, int sr, int l, int r, int i = 1) {
// cout << i << " " << r << " " << sr << "\n";
push_lazy(i);
if (sl == l && sr == r) {
return {segment_tree_sum[i], segment_tree_min[i], segment_tree_max[i]};
}
// push_lazy(i);
vector<int> ans = {0, 0, 0};
int mid = (sl + sr) / 2;
if (l <= mid) {
vector<int> q = query(sl, mid, l, min(mid, r), i*2);
ans[0] += q[0];
ans[1] = min(ans[1], q[1]);
ans[2] = max(ans[2], q[2]);
}
if (r > mid) {
vector<int> q = query(mid+1, sr, max(mid+1, l), r, i*2+1);
ans[0] += q[0];
ans[1] = min(ans[1], q[1]);
ans[2] = max(ans[2], q[2]);
}
return ans;
}
vector<int> distribute_candies(vector<int> c, vector<int> l,
vector<int> r, vector<int> v) {
int n = c.size();
int sr = log2(l.size()) + 1;
sr = (1 << sr);
int arr_size = (sr) * 2;
sr -= 1;
// cout << "size : " << arr_size << "\n";
segment_tree_sum = vector<int> (arr_size, 0);
segment_tree_min = vector<int> (arr_size, 0);
segment_tree_max = vector<int> (arr_size, 0);
lazy = vector<int> (arr_size, 0);
vector<vector<int>> ranges;
for (int k = 0; k < (int) l.size(); k++) {
ranges.push_back({l[k], k, v[k]});
ranges.push_back({r[k] + 1, k, -v[k]});
}
sort(ranges.begin(), ranges.end());
vector<int> ans(n);
int ptr = 0;
// line sweep on queries
for (auto p : ranges) {
int pos = p[0], val = p[2], q = p[1];
// cout << p[0] << " " << p[1] << " " << p[2] << " add\n";
if (pos != ptr) {
vector<int> res = query(0, sr, 0, sr); // get min and max
vector<int> back = query(0, sr, sr, sr); // get the final value
// cout << "res : " << res[0] << " " << res[1] << " " << res[2] << "\n";
// cout << "back: " << back[0]<< " " << back[1]<< " " << back[2]<< "\n";
// update boxes
while (pos != ptr) {
// cout << "ptr " << ptr << "\n";
int candies = back[0];
int too_many = 0, too_few = 0;
if (res[2] > c[ptr]) {
too_many = res[2] - c[ptr];
}
if (res[1] - too_many < 0) too_few = 0 - (res[1] - too_many);
// cout << candies << " " << too_many << " " << too_few << " -p\n";
candies += too_few - too_many;
candies = min(candies, c[ptr]);
candies = max(0, candies);
ans[ptr] = candies;
ptr++;
}
}
add(0, sr, q, sr, val);
/*
for (int k = 0; k < (int) segment_tree_sum.size(); k++) cout << segment_tree_sum[k] << " ";
cout << "\n";
for (int k = 0; k < (int) segment_tree_sum.size(); k++) cout << segment_tree_min[k] << " ";
cout << "\n";
for (int k = 0; k < (int) segment_tree_sum.size(); k++) cout << segment_tree_max[k] << " ";
cout << "\n";
for (int k = 0; k < (int) segment_tree_sum.size(); k++) cout << lazy[k] << " ";
cout << "\n";
*/
}
return ans;
}
/*
0 87 25 62 18 7 26 36 10 8 4 3 8 18 18 18 5 5 8 0 0 4 4 -1 -1 9 9 9 9 9 9 9
0 -1 -1 -1 0 -1 -1 9 5 0 0 -1 -1 9 9 9 5 5 8 0 0 4 4 -1 -1 9 9 9 9 9 9 9
0 9 8 9 8 4 9 9 5 8 4 4 9 9 9 9 5 5 8 0 0 4 4 -1 -1 9 9 9 9 9 9 9
0 -3 -17 14 0 -17 2 12 4 -4 -8 -9 -4 6 6 6 5 -1 2 -6 -6 -2 -2 -7 -7 3 3 3 3 3 3 3
0 -7 -7 -7 -6 -7 -7 3 -1 -6 -6 -7 -7 3 3 3 5 -1 2 -6 -6 -2 -2 -7 -7 3 3 3 3 3 3 3
0 5 5 3 5 -2 3 3 5 2 -2 -2 3 3 3 3 5 -1 2 -6 -6 -2 -2 -7 -7 3 3 3 3 3 3 3
0 101 23 78 8 15 34 44 4 4 8 7 12 22 22 22 5 -1 2 2 2 6 6 1 1 11 11 11 11 11 11 11
0 -1 -1 1 -1 1 1 11 -1 2 2 1 1 11 11 11 5 -1 2 2 2 6 6 1 1 11 11 11 11 11 11 11
0 11 6 11 5 6 11 11 5 2 6 6 11 11 11 11 5 -1 2 2 2 6 6 1 1 11 11 11 11 11 11 11
0 121 27 94 8 19 42 52 4 4 8 11 16 26 26 26 5 -1 2 2 2 6 8 3 3 13 13 13 13 13 13 13
0 -1 -1 3 -1 2 3 13 -1 2 2 3 3 13 13 13 5 -1 2 2 2 6 8 3 3 13 13 13 13 13 13 13
0 13 8 13 5 8 13 13 5 2 6 8 13 13 13 13 5 -1 2 2 2 6 8 3 3 13 13 13 13 13 13 13
0 41 -13 54 -12 -1 22 32 -6 -6 -2 1 6 16 16 16 0 -6 -3 -3 -3 1 3 -2 -2 8 8 8 8 8 8 8
0 -6 -6 -2 -6 -3 -2 8 -6 -3 -3 -2 -2 8 8 8 0 -6 -3 -3 -3 1 3 -2 -2 8 8 8 8 8 8 8
0 8 3 8 0 3 8 8 0 -3 1 3 8 8 8 8 0 -6 -3 -3 -3 1 3 -2 -2 8 8 8 8 8 8 8
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
813 ms |
42336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
