#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int M[1000000] = {0}, m[1000000] = {0}, lazy[1000000] = {0};
void push(int v)
{
M[2 * v] += lazy[v];
M[2 * v + 1] += lazy[v];
m[2 * v] += lazy[v];
m[2 * v + 1] += lazy[v];
lazy[2 * v] += lazy[v];
lazy[2 * v + 1] += lazy[v];
lazy[v] = 0;
}
void update(int v, int tl, int tr, int l, int r, int dx)
{
if (r < tl || tr < l)
return;
if (l <= tl && tr <= r)
{
M[v] += dx;
m[v] += dx;
lazy[v] += dx;
return;
}
push(v);
int tm = (tl + tr) / 2;
update(2 * v, tl, tm, l, r, dx);
update(2 * v + 1, tm + 1, tr, l, r, dx);
M[v] = max(M[2 * v], M[2 * v + 1]);
m[v] = min(m[2 * v], m[2 * v + 1]);
}
int Max(int v, int tl, int tr, int l, int r)
{
if (r < tl || tr < l)
return INT_MIN;
if (l <= tl && tr <= r)
return M[v];
push(v);
int tm = (tl + tr) / 2;
return max(
Max(2 * v, tl, tm, l, r),
Max(2 * v + 1, tm + 1, tr, l, r)
);
}
int Min(int v, int tl, int tr, int l, int r)
{
if (r < tl || tr < l)
return INT_MAX;
if (l <= tl && tr <= r)
return m[v];
push(v);
int tm = (tl + tr) / 2;
return min(
Min(2 * v, tl, tm, l, r),
Min(2 * v + 1, tm + 1, tr, l, r)
);
}
int query(int c, int q)
{
int lo = 0, hi = q;
while (lo < hi)
{
int mid = (lo + hi + 1) / 2;
if (Max(1, 0, q + 1, mid, q + 1) - Min(1, 0, q + 1, mid, q + 1) <= c)
hi = mid - 1;
else
lo = mid;
}
lo = hi;
if (Max(1, 0, q + 1, lo + 1, lo + 1) < Max(1, 0, q + 1, lo, lo))
return Max(1, 0, q + 1, q + 1, q + 1) - Max(1, 0, q + 1, lo + 1, lo + 1);
else
return c + Max(1, 0, q + 1, q + 1, q + 1) - Max(1, 0, q + 1, lo + 1, lo + 1);
}
struct Event
{
int idx, val, time;
};
bool operator<(const Event &A, const Event &B)
{
return A.idx < B.idx;
}
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v)
{
int n = c.size(), q = v.size();
vector<Event> events;
events.push_back({-1, 1000000000, -1});
events.push_back({-2, -1000000000, -2});
for (int i = 0; i < q; i++)
{
events.push_back({l[i], v[i], i});
events.push_back({r[i] + 1, -v[i], i});
}
sort(events.begin(), events.end());
vector<int> s(n);
int j = 0, sum = 0;
for (int i = 0; i < n; i++)
{
while (j < events.size() && events[j].idx <= i)
{
sum += events[j].val;
update(1, 0, q + 1, events[j].time + 2, q + 1, events[j].val);
j++;
}
s[i] = query(c[i], q);
}
return s;
}
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:115:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
115 | while (j < events.size() && events[j].idx <= i)
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1570 ms |
18220 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
