// In the name of Allah
#include <bits/stdc++.h>
#include "candies.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define endl '\n'
#define sep ' '
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
#define pb push_back
#define Mp make_pair
const int maxn = 2e5 + 4;
const ll oo = 1e18 + 4;
struct node {
int lazy0;
pll addx; pll val;
};
int n, q;
pll A[maxn]; pair<pii, ll> Q[maxn];
vector<int> ans; node t[4 * maxn];
void addx(int v, ll x) {
ll d = min(x, t[v].addx.S);
t[v].addx.S -= d; x -= d; t[v].addx.F += x;
t[v].val.F += x; t[v].val.F = min(t[v].val.S, t[v].val.F);
}
void subx(int v, ll x) {
t[v].addx.S += x;
t[v].val.F -= x; t[v].val.F = max(0ll, t[v].val.F);
}
void setx(int v) {
t[v].lazy0 = 1; t[v].addx = Mp(0, 0);
t[v].val.F = 0;
}
node f(node a, node b) {
node res;
res.lazy0 = 0; res.addx = Mp(0, 0);
res.val = b.val;
return res;
}
void shift(int v, int tl, int tr) {
int set0 = t[v].lazy0; t[v].lazy0 = 0;
pll x = t[v].addx; t[v].addx = Mp(0, 0);
if (tr - tl == 1) return ;
for (int u : {2 * v + 1, 2 * v + 2}) {
if (set0) setx(u);
addx(u, x.F); subx(u, x.S);
}
}
void build(int v, int tl, int tr) {
t[v].lazy0 = 0; t[v].addx = Mp(0, 0);
if (tr - tl == 1) {
t[v].val = Mp(0, A[tl].F);
return ;
}
int mid = (tl + tr) / 2;
build(2 * v + 1, tl, mid); build(2 * v + 2, mid, tr);
t[v] = f(t[2 * v + 1], t[2 * v + 2]);
}
void add_val(int v, int tl, int tr, int l, int r, ll x) {
l = max(l, tl); r = min(r, tr);
if (l >= tr || r <= tl) return ;
shift(v, tl, tr);
if (l == tl && r == tr) {
addx(v, x);
return ;
}
int mid = (tl + tr) / 2;
add_val(2 * v + 1, tl, mid, l, r, x); add_val(2 * v + 2, mid, tr, l, r, x);
t[v] = f(t[2 * v + 1], t[2 * v + 2]);
}
void sub_val(int v, int tl, int tr, int l, int r, ll x) {
l = max(l, tl); r = min(r, tr);
if (l >= tr || r <= tl) return ;
shift(v, tl, tr);
if (l == tl && r == tr) {
subx(v, x);
return ;
}
int mid = (tl + tr) / 2;
sub_val(2 * v + 1, tl, mid, l, r, x); sub_val(2 * v + 2, mid, tr, l, r, x);
t[v] = f(t[2 * v + 1], t[2 * v + 2]);
}
void set_zero(int v, int tl, int tr, int l, int r) {
l = max(l, tl); r = min(r, tr);
if (l >= tr || r <= tl) return ;
shift(v, tl, tr);
if (l == tl && r == tr) {
setx(v);
return ;
}
int mid = (tl + tr) / 2;
set_zero(2 * v + 1, tl, mid, l, r); set_zero(2 * v + 2, mid, tr, l, r);
t[v] = f(t[2 * v + 1], t[2 * v + 2]);
}
int get_ind(int v, int tl, int tr, int x) {
shift(v, tl, tr);
if (tr - tl == 1) {
if (t[v].val.F >= x) return tl;
else return tr;
}
int mid = (tl + tr) / 2;
if (t[2 * v + 1].val.F >= x) return get_ind(2 * v + 1, tl, mid, x);
else return get_ind(2 * v + 2, mid, tr, x);
}
void get_ans(int v, int tl, int tr) {
shift(v, tl, tr);
if (tr - tl == 1) {
ans[A[tl].S] = t[v].val.F;
return ;
}
int mid = (tl + tr) / 2;
get_ans(2 * v + 1, tl, mid); get_ans(2 * v + 2, mid, tr);
}
vector<int> distribute_candies(vector<int> c, vector<int> lx, vector<int> rx, vector<int> vx) {
n = len(c); q = len(lx);
for (int i = 0; i < n; i++) A[i] = Mp(c[i], i);
for (int i = 0; i < q; i++) Q[i] = Mp(Mp(lx[i], rx[i] + 1), vx[i]);
sort(A, A + n);
build(0, 0, n);
for (int i = 0; i < q; i++) {
int l = Q[i].F.F, r = Q[i].F.S, x = Q[i].S;
if (x >= 0) add_val(0, 0, n, 0, n, x);
else {
x = -x;
int j = get_ind(0, 0, n, x);
set_zero(0, 0, n, 0, j); sub_val(0, 0, n, j, n, x);
}
}
ans.clear(); ans.resize(n);
get_ans(0, 0, n);
return ans;
}
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:145:7: warning: unused variable 'l' [-Wunused-variable]
145 | int l = Q[i].F.F, r = Q[i].F.S, x = Q[i].S;
| ^
candies.cpp:145:21: warning: unused variable 'r' [-Wunused-variable]
145 | int l = Q[i].F.F, r = Q[i].F.S, x = Q[i].S;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
35416 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
35420 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
96 ms |
50512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
35416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
35420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
35416 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
35420 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
