#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define REP(i, j, k) for (int i = j; i < k; i++)
#define RREP(i, j, k) for (int i = j; i >= k; i--)
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1 : 0;}
typedef long long ll;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(x) x.begin(), x.end()
#define pb emplace_back
typedef vector<int> vi;
typedef vector<ii> vii;
#ifdef DEBUG
#define debug(args...) _debug(args)
void _debug(const char* format, ...) {
va_list args;
va_start(args, format);
vprintf(format, args);
va_end(args);
}
#else
#define debug(args...)
#endif
#define INF 1000000005
#define LINF 1000000000000000005
#define MAXN 200005
int n, q;
vi c;
vi ans;
vi qs[MAXN], qe[MAXN];
#define MLR int mid = lo + hi >> 1; int lc = u * 2, rc = u * 2 + 1
ll mx[MAXN * 4], mn[MAXN * 4], lazy[MAXN * 4];
void propo(int u, int lo, int hi) {
if (lazy[u] == 0 || lo == hi) return;
MLR;
mx[lc] += lazy[u];
mn[lc] += lazy[u];
mx[rc] += lazy[u];
mn[rc] += lazy[u];
lazy[lc] += lazy[u];
lazy[rc] += lazy[u];
lazy[u] = 0;
}
void incre(int s, int e, int x, int u, int lo, int hi) {
if (lo >= s && hi <= e) {
lazy[u] += x;
mn[u] += x;
mx[u] += x;
return;
}
propo(u, lo, hi);
MLR;
if (s <= mid) incre(s, e, x, lc, lo, mid);
if (e > mid) incre(s, e, x, rc, mid + 1, hi);
mn[u] = min(mn[lc], mn[rc]);
mx[u] = max(mx[lc], mx[rc]);
}
void incre(int s, int e, int x) {
incre(s, e, x, 1, 0, q);
}
ll getmax(int s, int e, int u, int lo, int hi) {
if (lo >= s && hi <= e) {
return mx[u];
}
propo(u, lo, hi);
MLR;
if (e <= mid) return getmax(s, e, lc, lo, mid);
else if (s > mid) return getmax(s, e, rc, mid + 1, hi);
else return max(getmax(s, e, lc, lo, mid), getmax(s, e, rc, mid + 1, hi));
}
ll getmax(int s, int e) {
return getmax(s, e, 1, 0, q);
}
ll getmin(int s, int e, int u, int lo, int hi) {
if (lo >= s && hi <= e) {
return mn[u];
}
propo(u, lo, hi);
MLR;
if (e <= mid) return getmin(s, e, lc, lo, mid);
else if (s > mid) return getmin(s, e, rc, mid + 1, hi);
else return min(getmin(s, e, lc, lo, mid), getmin(s, e, rc, mid + 1, hi));
}
ll getmin(int s, int e) {
return getmin(s, e, 1, 0, q);
}
int upper(int x, ll pmn, ll pmx, int u, int lo, int hi) {
if (lo == hi) {
return lo;
}
propo(u, lo, hi);
MLR;
int npmn = min(pmn, mn[rc]), npmx = max(pmx, mx[rc]);
if (npmx - npmn > x) {
return upper(x, pmn, pmx, rc, mid + 1, hi);
} else {
return upper(x, npmn, npmx, lc, lo, mid);
}
}
int upper(int s, ll pmn, ll pmx) {
return upper(s, pmn, pmx, 1, 0, q);
}
vi distribute_candies(vi c, vi l, vi r, vi v) {
::c = c;
n = c.size(); q = l.size();
l.insert(l.begin(), 0);
r.insert(r.begin(), 0);
v.insert(v.begin(), 0);
REP (i, 1, q + 1) {
qs[l[i]].pb(i);
qe[r[i]].pb(i);
}
ans.resize(n);
REP (i, 0, n) {
for (int &j : qs[i]) {
incre(j, q, v[j]);
debug(" incre %d %d: %d\n", j, q, v[j]);
}
ll sum = getmax(q, q);
debug("%lld %lld %lld\n", sum, mx[1], mn[1]);
if (mx[1] - mn[1] <= c[i]) {
ans[i] = sum - mn[1];
} else {
int id = upper(c[i], LINF, -LINF);
ll cur = getmax(id, id);
ll mn = getmin(id + 1, q);
ll mx = getmax(id + 1, q);
debug(" %d %lld %lld %lld\n", id, cur, mn, mx);
if (cur < mn) {
ans[i] = sum - (mx - c[i]);
} else {
ans[i] = sum - mn;
}
}
for (int &j : qe[i]) {
incre(j, q, -v[j]);
debug(" decre %d %d: %d\n", j, q, -v[j]);
}
}
return ans;
}
Compilation message
candies.cpp: In function 'void propo(int, int, int)':
candies.cpp:47:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
47 | #define MLR int mid = lo + hi >> 1; int lc = u * 2, rc = u * 2 + 1
| ~~~^~~~
candies.cpp:51:2: note: in expansion of macro 'MLR'
51 | MLR;
| ^~~
candies.cpp:47:17: warning: unused variable 'mid' [-Wunused-variable]
47 | #define MLR int mid = lo + hi >> 1; int lc = u * 2, rc = u * 2 + 1
| ^~~
candies.cpp:51:2: note: in expansion of macro 'MLR'
51 | MLR;
| ^~~
candies.cpp: In function 'void incre(int, int, int, int, int, int)':
candies.cpp:47:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
47 | #define MLR int mid = lo + hi >> 1; int lc = u * 2, rc = u * 2 + 1
| ~~~^~~~
candies.cpp:68:2: note: in expansion of macro 'MLR'
68 | MLR;
| ^~~
candies.cpp: In function 'll getmax(int, int, int, int, int)':
candies.cpp:47:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
47 | #define MLR int mid = lo + hi >> 1; int lc = u * 2, rc = u * 2 + 1
| ~~~^~~~
candies.cpp:82:2: note: in expansion of macro 'MLR'
82 | MLR;
| ^~~
candies.cpp: In function 'll getmin(int, int, int, int, int)':
candies.cpp:47:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
47 | #define MLR int mid = lo + hi >> 1; int lc = u * 2, rc = u * 2 + 1
| ~~~^~~~
candies.cpp:95:2: note: in expansion of macro 'MLR'
95 | MLR;
| ^~~
candies.cpp: In function 'int upper(int, ll, ll, int, int, int)':
candies.cpp:47:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
47 | #define MLR int mid = lo + hi >> 1; int lc = u * 2, rc = u * 2 + 1
| ~~~^~~~
candies.cpp:109:2: note: in expansion of macro 'MLR'
109 | MLR;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
9676 KB |
Output is correct |
| 2 |
Correct |
6 ms |
9676 KB |
Output is correct |
| 3 |
Correct |
9 ms |
9804 KB |
Output is correct |
| 4 |
Correct |
9 ms |
9804 KB |
Output is correct |
| 5 |
Correct |
10 ms |
9932 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
820 ms |
37824 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
9676 KB |
Output is correct |
| 2 |
Incorrect |
424 ms |
29596 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
9676 KB |
Output is correct |
| 2 |
Correct |
8 ms |
9676 KB |
Output is correct |
| 3 |
Correct |
198 ms |
29672 KB |
Output is correct |
| 4 |
Correct |
107 ms |
13892 KB |
Output is correct |
| 5 |
Correct |
313 ms |
32132 KB |
Output is correct |
| 6 |
Correct |
328 ms |
32132 KB |
Output is correct |
| 7 |
Incorrect |
349 ms |
32156 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
9676 KB |
Output is correct |
| 2 |
Correct |
6 ms |
9676 KB |
Output is correct |
| 3 |
Correct |
9 ms |
9804 KB |
Output is correct |
| 4 |
Correct |
9 ms |
9804 KB |
Output is correct |
| 5 |
Correct |
10 ms |
9932 KB |
Output is correct |
| 6 |
Incorrect |
820 ms |
37824 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
