#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;i++)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(),v.rend()
#define pb push_back
#define sz(a) (int)a.size()
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define GR(a,n,m) vector<vector<int>> a(n, vector<int>(m, 0));
struct segment_tree_beats{
static const int maxn = (1 << 20);
const ll inf = 1e17;
int n;
struct node{
ll max;
ll second_max;
int max_cnt;
ll min;
ll second_min;
int min_cnt;
ll sum;
ll lazy_add;
ll lazy_set;
} t[maxn];
void push_set(int i, int l, int r, ll val){
t[i].min = t[i].max = t[i].lazy_set = val;
t[i].min_cnt = t[i].max_cnt = r - l + 1;
t[i].second_max = -inf;
t[i].second_min = inf;
t[i].sum = val * (r - l + 1);
t[i].lazy_add = 0;
}
void push_min(int i, int l, int r, ll val){
if(t[i].min >= val){
push_set(i, l, r, val);
}else if(t[i].max > val){
if(t[i].second_min == t[i].max){
t[i].second_min = val;
}
t[i].sum -= (t[i].max - val) * t[i].max_cnt;
t[i].max = val;
}
}
void push_max(int i, int l, int r, ll val){
if(t[i].max <= val){
push_set(i, l, r, val);
}else if(t[i].min < val){
if(t[i].second_max == t[i].min){
t[i].second_max = val;
}
t[i].sum += (val - t[i].min) * t[i].min_cnt;
t[i].min = val;
}
}
void push_add(int i, int l, int r, ll val){
if(t[i].min == t[i].max){
push_set(i, l, r, t[i].max + val);
}else{
t[i].max += val, t[i].min += val;
if(t[i].second_max != -inf)t[i].second_max += val;
if(t[i].second_min != inf)t[i].second_min += val;
t[i].sum += val * (r - l + 1);
t[i].lazy_add += val;
}
}
void update_children(int i, int l, int r){
if(l == r)return;
int mid = l + r >> 1;
if(t[i].lazy_set != -1){
push_set(2 * i, l, mid, t[i].lazy_set);
push_set(2 * i + 1, mid + 1, r, t[i].lazy_set);
t[i].lazy_set = -1;
}else{
push_add(2 * i, l, mid, t[i].lazy_add);
push_add(2 * i + 1, mid + 1, r, t[i].lazy_add);
t[i].lazy_add = 0;
push_min(2 * i, l, mid, t[i].max);
push_min(2 * i + 1, mid + 1, r, t[i].max);
push_max(2 * i, l, mid, t[i].min);
push_max(2 * i + 1, mid + 1, r, t[i].min);
}
}
void merge(int i){
t[i].sum = t[2 * i].sum + t[2 * i + 1].sum;
t[i].max = max(t[2 * i].max, t[2 * i + 1].max);
t[i].second_max = max(t[2 * i].second_max, t[2 * i + 1].second_max);
t[i].max_cnt = 0;
if(t[2 * i].max == t[i].max){
t[i].max_cnt += t[2 * i].max_cnt;
}else{
t[i].second_max = max(t[i].second_max, t[2 * i].max);
}
if(t[2 * i + 1].max == t[i].max){
t[i].max_cnt += t[2 * i + 1].max_cnt;
}else{
t[i].second_max = max(t[i].second_max, t[2 * i + 1].max);
}
t[i].min = min(t[2 * i].min, t[2 * i + 1].min);
t[i].second_min = min(t[2 * i].second_min, t[2 * i + 1].second_min);
t[i].min_cnt = 0;
if(t[2 * i].min == t[i].min){
t[i].min_cnt += t[2 * i].min_cnt;
}else{
t[i].second_min = min(t[i].second_min, t[2 * i].min);
}
if(t[2 * i + 1].min == t[i].min){
t[i].min_cnt += t[2 * i + 1].min_cnt;
}else{
t[i].second_min = min(t[i].second_min, t[2 * i + 1].min);
}
}
void build(int i, int l, int r, vector<int>& a){
t[i].lazy_add = 0, t[i].lazy_set = -1;
if(l == r){
t[i].max = t[i].min = t[i].sum = a[l];
t[i].max_cnt = t[i].min_cnt = 1;
t[i].second_max = -inf;
t[i].second_min = inf;
}else{
int mid = l + r >> 1;
build(2 * i, l, mid, a);
build(2 * i + 1, mid + 1, r, a);
merge(i);
}
}
void update_min(int i, int l, int r, int tl, int tr, int val){
if(l > tr || r < tl || t[i].max <= val)return;
if(l >= tl && r <= tr && t[i].second_max < val){
push_min(i, l, r, val);
return;
}
update_children(i, l, r);
int mid = l + r >> 1;
update_min(2 * i, l, mid, tl, tr, val);
update_min(2 * i + 1, mid + 1, r, tl, tr, val);
merge(i);
}
void update_max(int i, int l, int r, int tl, int tr, int val){
if(l > tr || r < tl || t[i].min >= val)return;
if(l >= tl && r <= tr && t[i].second_min > val){
push_max(i, l, r, val);
return;
}
update_children(i, l, r);
int mid = l + r >> 1;
update_max(2 * i, l, mid, tl, tr, val);
update_max(2 * i + 1, mid + 1, r, tl, tr, val);
merge(i);
}
void update_set(int i, int l, int r, int tl, int tr, int val){
if(l > tr || r < tl)return;
if(l >= tl && r <= tr){
push_set(i, l, r, val);
return;
}
update_children(i, l, r);
int mid = l + r >> 1;
update_set(2 * i, l, mid, tl, tr, val);
update_set(2 * i + 1, mid + 1, r, tl, tr, val);
merge(i);
}
void update_add(int i, int l, int r, int tl, int tr, int val){
if(l > tr || r < tl)return;
if(l >= tl && r <= tr){
push_add(i, l, r, val);
return;
}
update_children(i, l, r);
int mid = l + r >> 1;
update_add(2 * i, l, mid, tl, tr, val);
update_add(2 * i + 1, mid + 1, r, tl, tr, val);
merge(i);
}
ll query_sum(int i, int l, int r, int tl, int tr){
if(l > tr || r < tl)return 0;
if(l >= tl && r <= tr)return t[i].sum;
update_children(i, l, r);
int mid = l + r >> 1;
return (query_sum(2 * i, l, mid, tl, tr) + query_sum(2 * i + 1, mid + 1, r, tl, tr));
}
ll query_min(int i, int l, int r, int tl, int tr){
if(l > tr || r < tl)return inf;
if(l >= tl && r <= tr)return t[i].min;
update_children(i, l, r);
int mid = l + r >> 1;
return min(query_min(2 * i, l, mid, tl, tr), query_min(2 * i + 1,mid + 1, r, tl, tr));
}
ll query_max(int i, int l, int r, int tl, int tr){
if(l > tr || r < tl)return -inf;
if(l >= tl && r <= tr)return t[i].max;
update_children(i, l, r);
int mid = l + r >> 1;
return max(query_max(2 * i, l, mid, tl, tr), query_max(2 * i + 1,mid + 1, r, tl, tr));
}
void build(vector<int>& a){
n = sz(a);
build(1, 0, n - 1, a);
}
void update_add(int l, int r, int val){
update_add(1, 0, n - 1, l, r, val);
}
void update_set(int l, int r, int val){
update_set(1, 0, n - 1, l, r, val);
}
void update_max(int l, int r, int val){
update_max(1, 0, n - 1, l, r, val);
}
void update_min(int l, int r, int val){
update_min(1, 0, n - 1, l, r, val);
}
ll query_sum(int l, int r){
return query_sum(1, 0, n - 1, l, r);
}
ll query_min(int l, int r){
return query_min(1, 0, n - 1, l, r);
}
ll query_max(int l, int r){
return query_max(1, 0, n - 1, l, r);
}
};
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v)
{
int n = sz(c);
int q = sz(l);
vector<int> ans(n, 0);
set<int> s;
for(auto x: c)s.insert(x);
bool all_pos = true;
for(auto x: v)if(x < 0)all_pos = false;
if(n <= 2000 && q <= 2000){
for(int j = 0;j < q;j++){
for(int i = l[j];i <= r[j];i++){
ans[i] = max(ans[i] + v[j], 0);
ans[i] = min(ans[i], c[i]);
}
}
return ans;
}
if(all_pos){
vector<ll> p(n + 5, 0);
for(int j = 0;j < q;j++){
p[l[j]] += v[j];
p[r[j] + 1] -= v[j];
}
for(int i = 1;i < n;i++)
p[i] += p[i - 1];
vector<ll> tmp(n);
forn(i,n){
tmp[i] = min((ll)c[i], p[i]);
ans[i] = tmp[i];
}
return ans;
}
if(sz(s) == 1){
vector<int> a(n, 0);
segment_tree_beats st;
st.build(a);
for(int i = 0;i < q;i++){
st.update_add(l[i], r[i], v[i]);
st.update_max(l[i],r[i], 0);
st.update_min(l[i],r[i], c[0]);
}
for(int i = 0;i < n;i++){
ans[i] = st.query_sum(i,i);
}
return ans;
}
}
Compilation message
candies.cpp: In member function 'void segment_tree_beats::update_children(int, int, int)':
candies.cpp:93:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
93 | int mid = l + r >> 1;
| ~~^~~
candies.cpp: In member function 'void segment_tree_beats::build(int, int, int, std::vector<int>&)':
candies.cpp:161:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
161 | int mid = l + r >> 1;
| ~~^~~
candies.cpp: In member function 'void segment_tree_beats::update_min(int, int, int, int, int, int)':
candies.cpp:181:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
181 | int mid = l + r >> 1;
| ~~^~~
candies.cpp: In member function 'void segment_tree_beats::update_max(int, int, int, int, int, int)':
candies.cpp:200:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
200 | int mid = l + r >> 1;
| ~~^~~
candies.cpp: In member function 'void segment_tree_beats::update_set(int, int, int, int, int, int)':
candies.cpp:218:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
218 | int mid = l + r >> 1;
| ~~^~~
candies.cpp: In member function 'void segment_tree_beats::update_add(int, int, int, int, int, int)':
candies.cpp:235:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
235 | int mid = l + r >> 1;
| ~~^~~
candies.cpp: In member function 'long long int segment_tree_beats::query_sum(int, int, int, int, int)':
candies.cpp:250:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
250 | int mid = l + r >> 1;
| ~~^~~
candies.cpp: In member function 'long long int segment_tree_beats::query_min(int, int, int, int, int)':
candies.cpp:262:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
262 | int mid = l + r >> 1;
| ~~^~~
candies.cpp: In member function 'long long int segment_tree_beats::query_max(int, int, int, int, int)':
candies.cpp:274:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
274 | int mid = l + r >> 1;
| ~~^~~
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:320:14: warning: control reaches end of non-void function [-Wreturn-type]
320 | set<int> s;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
44 ms |
74052 KB |
Output is correct |
| 2 |
Correct |
42 ms |
74028 KB |
Output is correct |
| 3 |
Correct |
48 ms |
74132 KB |
Output is correct |
| 4 |
Correct |
43 ms |
74096 KB |
Output is correct |
| 5 |
Correct |
47 ms |
74188 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
256 ms |
89784 KB |
Output is correct |
| 2 |
Correct |
210 ms |
88492 KB |
Output is correct |
| 3 |
Correct |
260 ms |
88416 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
44 ms |
74052 KB |
Output is correct |
| 2 |
Correct |
304 ms |
78896 KB |
Output is correct |
| 3 |
Correct |
216 ms |
77576 KB |
Output is correct |
| 4 |
Correct |
892 ms |
82004 KB |
Output is correct |
| 5 |
Correct |
1138 ms |
82004 KB |
Output is correct |
| 6 |
Correct |
1366 ms |
82004 KB |
Output is correct |
| 7 |
Correct |
1304 ms |
82008 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
43 ms |
74128 KB |
Output is correct |
| 2 |
Correct |
43 ms |
74140 KB |
Output is correct |
| 3 |
Runtime error |
199 ms |
159916 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
44 ms |
74052 KB |
Output is correct |
| 2 |
Correct |
42 ms |
74028 KB |
Output is correct |
| 3 |
Correct |
48 ms |
74132 KB |
Output is correct |
| 4 |
Correct |
43 ms |
74096 KB |
Output is correct |
| 5 |
Correct |
47 ms |
74188 KB |
Output is correct |
| 6 |
Correct |
256 ms |
89784 KB |
Output is correct |
| 7 |
Correct |
210 ms |
88492 KB |
Output is correct |
| 8 |
Correct |
260 ms |
88416 KB |
Output is correct |
| 9 |
Correct |
44 ms |
74052 KB |
Output is correct |
| 10 |
Correct |
304 ms |
78896 KB |
Output is correct |
| 11 |
Correct |
216 ms |
77576 KB |
Output is correct |
| 12 |
Correct |
892 ms |
82004 KB |
Output is correct |
| 13 |
Correct |
1138 ms |
82004 KB |
Output is correct |
| 14 |
Correct |
1366 ms |
82004 KB |
Output is correct |
| 15 |
Correct |
1304 ms |
82008 KB |
Output is correct |
| 16 |
Correct |
43 ms |
74128 KB |
Output is correct |
| 17 |
Correct |
43 ms |
74140 KB |
Output is correct |
| 18 |
Runtime error |
199 ms |
159916 KB |
Execution killed with signal 6 |
| 19 |
Halted |
0 ms |
0 KB |
- |
