#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;
const int N = (1 << 18);
ll up[2 * N];
pair<ll, int> mn[2 * N];
pair<ll, int> mx[2 * N];
void init() {
for (int i = 2 * N - 1; i >= 1; i--) {
if (i >= N)
mn[i].second = mx[i].second = i - N;
else
mn[i].second = mx[i].second = mn[2 * i].second;
mn[i].first = mx[i].first = 0;
}
}
void setpush(int v, int d) {
up[v] += d;
mn[v].first += d;
mx[v].first += d;
}
void push(int v) {
if (v >= N || !up[v]) return;
setpush(2 * v, up[v]);
setpush(2 * v + 1, up[v]);
up[v] = 0;
}
void update(int ql, int qr, int d, int l = 0, int r = N - 1, int v = 1) {
if (r < ql || l > qr)
return;
if (ql <= l && r <= qr) {
setpush(v, d);
return;
}
int mid = (l + r) / 2;
push(v);
update(ql, qr, d, l, mid, 2 * v);
update(ql, qr, d, mid + 1, r, 2 * v + 1);
mn[v] = min(mn[2 * v], mn[2 * v + 1]);
mx[v] = max(mx[2 * v], mx[2 * v + 1]);
}
int get(int pos, int l = 0, int r = N - 1, int v = 1) {
if (l == r)
return mn[v].first;
int mid = (l + r) / 2;
push(v);
if (pos <= mid)
return get(pos, l, mid, 2 * v);
return get(pos, mid + 1, r, 2 * v + 1);
}
pair<ll, int> get_min(int ql, int qr, int l = 0, int r = N - 1, int v = 1) {
if (r < ql || l > qr)
return {INF, 0};
if (ql <= l && r <= qr)
return mn[v];
int mid = (l + r) / 2;
push(v);
return min(get_min(ql, qr, l, mid, 2 * v),
get_min(ql, qr, mid + 1, r, 2 * v + 1));
}
pair<ll, int> get_max(int ql, int qr, int l = 0, int r = N - 1, int v = 1) {
if (r < ql || l > qr)
return {-INF, 0};
if (ql <= l && r <= qr)
return mx[v];
int mid = (l + r) / 2;
push(v);
return max(get_max(ql, qr, l, mid, 2 * v),
get_max(ql, qr, mid + 1, r, 2 * v + 1));
}
int calc(int c) {
int l = 0, r = N - 1;
while (r - l > 1) {
int mid = (l + r) / 2;
if (get_max(mid, N - 1).first - get_min(mid, N - 1).first >= c)
l = mid;
else
r = mid;
}
// cout << c << ":\n";
// cout << get_min(l, N - 1).first << ' ';
// cout << get_max(l, N - 1).first << '\n';
// cout << '\n';
if (get_min(l, N - 1).second < get_max(l, N - 1).second) {
return get(N - 1) - get_max(l, N - 1).first + c;
} else {
return get(N - 1) - get_min(l, N - 1).first;
}
}
vector<pair<ll, int>> upd[N];
vector<int> distribute_candies(vector<int> c, vector<int> l,
vector<int> r, vector<int> v) {
init();
update(0, 0, +INF);
int n = c.size(), q = l.size();
for (int i = 0; i < q; i++) {
upd[l[i]].push_back({v[i], i + 2});
upd[r[i]+1].push_back({-v[i], i + 2});
}
vector<int> s(n);
for (int i = 0; i < n; i++) {
for (auto [v, p] : upd[i])
update(p, N - 1, v);
s[i] = calc(c[i]);
}
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:107:18: warning: overflow in conversion from 'll' {aka 'long long int'} to 'int' changes value from '1000000000000000000' to '-1486618624' [-Woverflow]
107 | update(0, 0, +INF);
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
22872 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
23132 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1535 ms |
47696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
23132 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
23128 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
22872 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
23132 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
