#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second
//#pragma GCC optimize ("O3")
//#pragma GCC target("tune=native")
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
const int nax = 200 * 1000 + 10;
const ll INF = 1e18;
int n, q;
vector<pi>evs[nax];
struct Node {
ll g, mi, mx;
};
Node T[(1 << 19)];
void puttag(int v, int x) {
T[v].mi += x;
T[v].mx += x;
T[v].g += x;
}
void push(int v) {
puttag(v << 1, T[v].g);
puttag(v << 1 | 1, T[v].g);
T[v].g = 0;
}
void merge(int v) {
T[v].mi = min(T[v << 1].mi, T[v << 1 | 1].mi) + T[v].g;
T[v].mx = max(T[v << 1].mx, T[v << 1 | 1].mx) + T[v].g;
}
void upd(int a, int b, int x, int l = 0, int r = q, int v = 1) {
if(a <= l && r <= b) {
puttag(v, x);
return;
}
push(v);
int mid = (l + r) >> 1;
if(a <= mid) upd(a, b, x, l, mid, v << 1);
if(mid < b) upd(a, b, x, mid + 1, r, v << 1 | 1);
merge(v);
}
tuple<int,ll,ll,ll> ask(int k) {
int v = 1, l = 0, r = q;
ll mi = INF, mx = -INF;
while(l != r) {
int mid = (l + r) >> 1;
push(v);
if(max(mx, T[v << 1 | 1].mx) - min(mi, T[v << 1 | 1].mi) > k) {
v = v << 1 | 1;
l = mid + 1;
} else {
mx = max(mx, T[v << 1 | 1].mx);
mi = min(mi, T[v << 1 | 1].mi);
v = v << 1;
r = mid;
}
}
mi = min(mi, T[v].mi);
mx = max(mx, T[v].mx);
return {l, mi, mx, T[v].mi};
}
vi distribute_candies(vi _c, vi _l, vi _r, vi _v) {
n = (int)_c.size();
q = (int)_l.size();
for(int i = 0; i < q; ++i) {
evs[_l[i]].emplace_back(i + 1, _v[i]);
evs[_r[i] + 1].emplace_back(i + 1, -_v[i]);
}
vi ans(n);
ll sum = 0;
for(int i = 0; i < n; ++i) {
for(auto &[a,b] : evs[i]) {
upd(a, q, b);
sum += b;
}
auto [p, a, b, val] = ask(_c[i]);
if(val == a) {
//cerr << _c[i] + sum - b << "\n";
ans[i] = _c[i] + sum - b;
} else {
//cerr << sum - a << "\n";
ans[i] = sum - a;
}
//cerr << "MY VAL: " << sum - a << " " << sum - b << "\n";
}
return ans;
}
//int main() {
//ios_base::sync_with_stdio(0);
//cin.tie(0);
//distribute_candies({10, 15, 13}, {0, 0}, {2, 1}, {20, -11});
//}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
337 ms |
36112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
