// In the name of Allah
#include <bits/stdc++.h>
#include "candies.h"
using namespace std;
typedef __int128 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 {
ll val;
pll lazym; ll lazys;
};
int n, q;
int A[maxn]; pair<pii, int> Q[maxn];
int val[maxn]; vector<int> ans;
node t[4 * maxn];
void solve1() {
for (int i = 0; i < q; i++) {
int l = Q[i].F.F, r = Q[i].F.S, x = Q[i].S;
for (int j = l; j < r; j++) {
val[j] += x;
val[j] = (val[j] >= 0) ? val[j] : 0;
val[j] = (val[j] <= A[j]) ? val[j] : A[j];
}
}
}
void shift(int v, int tl, int tr) {
ll x1 = t[v].lazym.F, x2 = t[v].lazym.S, R = t[v].lazys;
t[v].lazym = Mp(oo, -oo); t[v].lazys = 0;
if (tr - tl == 1) return ;
for (int u : {2 * v + 1, 2 * v + 2}) {
t[u].val = min(t[u].val, x1); t[u].val = max(t[u].val, x2);
t[u].val += R;
t[u].lazym.F = min(t[u].lazym.F, x1 - t[u].lazys);
t[u].lazym.S = max(t[u].lazym.S, x2 - t[u].lazys);
if (t[u].lazym.S > t[u].lazym.F) t[u].lazym.F = t[u].lazym.S;
t[u].lazys += R;
}
}
void build(int v, int tl, int tr) {
t[v].val = 0;
t[v].lazym = Mp(oo, -oo); t[v].lazys = 0;
if (tr - tl == 1) return ;
int mid = (tl + tr) / 2;
build(2 * v + 1, tl, mid); build(2 * v + 2, mid, tr);
}
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) {
t[v].val += x; t[v].lazys += 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);
}
void set_min(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) {
t[v].val = min(t[v].val, x);
t[v].lazym.F = min(t[v].lazym.F, x);
if (t[v].lazym.S > t[v].lazym.F) t[v].lazym.F = t[v].lazym.S;
return ;
}
int mid = (tl + tr) / 2;
set_min(2 * v + 1, tl, mid, l, r, x); set_min(2 * v + 2, mid, tr, l, r, x);
}
void set_max(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) {
t[v].val = max(t[v].val, x);
t[v].lazym.S = max(t[v].lazym.S, x);
if (t[v].lazym.S > t[v].lazym.F) t[v].lazym.F = t[v].lazym.S;
return ;
}
int mid = (tl + tr) / 2;
set_max(2 * v + 1, tl, mid, l, r, x); set_max(2 * v + 2, mid, tr, l, r, x);
}
void get_res(int v, int tl, int tr) {
shift(v, tl, tr);
if (tr - tl == 1) {
val[tl] = max((ll) 0, min((ll) A[tl], (ll) t[v].val));
return ;
}
int mid = (tl + tr) / 2;
get_res(2 * v + 1, tl, mid); get_res(2 * v + 2, mid, tr);
}
void solve2() {
int mx = *max_element(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;
add_val(0, 0, n, l, r, x);
if (x < 0) set_max(0, 0, n, 0, n, 0);
else set_min(0, 0, n, 0, n, mx);
}
get_res(0, 0, n);
}
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
n = len(c); q = len(l);
for (int i = 0; i < n; i++) A[i] = c[i];
for (int i = 0; i < q; i++) Q[i] = Mp(Mp(l[i], r[i] + 1), v[i]);
fill(val, val + n, 0);
if (n <= 2000 && q <= 2000) solve1();
else solve2();
ans.clear(); ans.resize(n);
for (int i = 0; i < n; i++) ans[i] = val[i];
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
53852 KB |
Output is correct |
| 2 |
Correct |
4 ms |
53852 KB |
Output is correct |
| 3 |
Correct |
6 ms |
53980 KB |
Output is correct |
| 4 |
Correct |
5 ms |
53936 KB |
Output is correct |
| 5 |
Correct |
7 ms |
53848 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
272 ms |
62292 KB |
Output is correct |
| 2 |
Correct |
264 ms |
62228 KB |
Output is correct |
| 3 |
Correct |
262 ms |
62224 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
53852 KB |
Output is correct |
| 2 |
Incorrect |
129 ms |
58696 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
53852 KB |
Output is correct |
| 2 |
Correct |
5 ms |
53852 KB |
Output is correct |
| 3 |
Incorrect |
38 ms |
58636 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
53852 KB |
Output is correct |
| 2 |
Correct |
4 ms |
53852 KB |
Output is correct |
| 3 |
Correct |
6 ms |
53980 KB |
Output is correct |
| 4 |
Correct |
5 ms |
53936 KB |
Output is correct |
| 5 |
Correct |
7 ms |
53848 KB |
Output is correct |
| 6 |
Correct |
272 ms |
62292 KB |
Output is correct |
| 7 |
Correct |
264 ms |
62228 KB |
Output is correct |
| 8 |
Correct |
262 ms |
62224 KB |
Output is correct |
| 9 |
Correct |
5 ms |
53852 KB |
Output is correct |
| 10 |
Incorrect |
129 ms |
58696 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
