#include "candies.h"
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>
#define ll long long
using namespace std;
const int MX = 2e5 + 5;
struct T{
int mx1, mx2;
int mn1, mn2;
ll lazy;
T() {
mx1 = 0;
mx2 = -INT_MAX;
mn1 = 0;
mn2 = INT_MAX;
lazy = 0;
}
} tree[4 * MX];
int n, q, cc;
vector<int> ans;
void get_value(int id) {
if(tree[id * 2 + 1].mx1 == tree[id * 2 + 2].mx1) {
tree[id].mx1 = tree[id * 2 + 1].mx1;
tree[id].mx2 = max(tree[id * 2 + 1].mx2, tree[id * 2 + 2].mx2);
}
if(tree[id * 2 + 1].mx1 < tree[id * 2 + 2].mx1) {
tree[id].mx1 = tree[id * 2 + 2].mx1;
tree[id].mx2 = max(tree[id * 2 + 1].mx1, tree[id * 2 + 2].mx2);
}
if(tree[id * 2 + 1].mx1 > tree[id * 2 + 2].mx1) {
tree[id].mx1 = tree[id * 2 + 1].mx1;
tree[id].mx2 = max(tree[id * 2 + 2].mx1, tree[id * 2 + 1].mx2);
}
if(tree[id * 2 + 1].mn1 == tree[id * 2 + 2].mn1) {
tree[id].mn1 = tree[id * 2 + 1].mn1;
tree[id].mn2 = min(tree[id * 2 + 1].mn2, tree[id * 2 + 2].mn2);
}
if(tree[id * 2 + 1].mn1 < tree[id * 2 + 2].mn1) {
tree[id].mn1 = tree[id * 2 + 2].mn1;
tree[id].mn2 = min(tree[id * 2 + 1].mn1, tree[id * 2 + 2].mn2);
}
if(tree[id * 2 + 1].mn1 > tree[id * 2 + 2].mn1) {
tree[id].mn1 = tree[id * 2 + 1].mn1;
tree[id].mn2 = min(tree[id * 2 + 2].mn1, tree[id * 2 + 1].mn2);
}
}
void propagate(int id, int l, int r) {
if(l == r || !tree[id].lazy) return;
tree[id * 2 + 1].lazy += tree[id].lazy;
tree[id * 2 + 1].mx1 += tree[id].lazy;
tree[id * 2 + 1].mx1 = min(tree[id * 2 + 1].mx1, tree[id].mx1);
tree[id * 2 + 1].mx1 = max(tree[id * 2 + 1].mx1, tree[id].mn1);
tree[id * 2 + 1].mn1 += tree[id].lazy;
tree[id * 2 + 1].mn1 = max(tree[id * 2 + 1].mn1, tree[id].mn1);
tree[id * 2 + 1].mn1 = min(tree[id * 2 + 1].mn1, tree[id].mx1);
if(tree[id * 2 + 1].mx1 != tree[id * 2 + 1].mn1) {
if(tree[id * 2 + 1].mx2 != -INT_MAX) {
tree[id * 2 + 1].mx2 += tree[id].lazy;
tree[id * 2 + 1].mx2 = min(tree[id * 2 + 1].mx2, tree[id * 2 + 1].mx1);
}
if(tree[id * 2 + 1].mn2 != INT_MAX) {
tree[id * 2 + 1].mn2 += tree[id].lazy;
tree[id * 2 + 1].mn2 = max(tree[id * 2 + 1].mn2, tree[id * 2 + 1].mn1);
}
}
tree[id * 2 + 2].lazy += tree[id].lazy;
tree[id * 2 + 2].mx1 += tree[id].lazy;
tree[id * 2 + 2].mx1 = min(tree[id * 2 + 2].mx1, tree[id].mx1);
tree[id * 2 + 2].mx1 = max(tree[id * 2 + 2].mx1, tree[id].mn1);
tree[id * 2 + 2].mn1 += tree[id].lazy;
tree[id * 2 + 2].mn1 = max(tree[id * 2 + 2].mn1, tree[id].mn1);
tree[id * 2 + 2].mn1 = min(tree[id * 2 + 2].mn1, tree[id].mx1);
if(tree[id * 2 + 2].mx1 != tree[id * 2 + 2].mn1) {
if(tree[id * 2 + 2].mx2 != -INT_MAX) {
tree[id * 2 + 2].mx2 += tree[id].lazy;
tree[id * 2 + 2].mx2 = min(tree[id * 2 + 2].mx2, tree[id * 2 + 2].mx1);
}
if(tree[id * 2 + 2].mn2 != INT_MAX) {
tree[id * 2 + 2].mn2 += tree[id].lazy;
tree[id * 2 + 2].mn2 = max(tree[id * 2 + 2].mn2, tree[id * 2 + 2].mn1);
}
}
tree[id].lazy = 0;
get_value(id);
}
void add(int id, int l, int r, int L, int R, int x) {
if(L > r || l > R) return;
if(L <= l && r <= R) {
tree[id].mx1 += x;
if(tree[id].mx2 > -INT_MAX) tree[id].mx2 += x;
tree[id].mn1 += x;
if(tree[id].mn2 > INT_MAX) tree[id].mn2 += x;
tree[id].lazy += x;
return;
}
propagate(id, l, r);
int mid = (l + r) / 2;
add(id * 2 + 1, l, mid, L, R, x);
add(id * 2 + 2, mid + 1, r, L, R, x);
get_value(id);
}
void minn(int id, int l, int r, int L, int R) {
if(L > r || l > R || tree[id].mx1 <= cc) return;
if(L <= l && r <= R && tree[id].mx2 < cc) {
tree[id].mx1 = cc;
return;
}
propagate(id, l, r);
int mid = (l + r) / 2;
minn(id * 2 + 1, l, mid, L, R);
minn(id * 2 + 2, mid + 1, r, L, R);
get_value(id);
}
void maxx(int id, int l, int r, int L, int R) {
if(L > r || l > R || tree[id].mn1 >= 0) return;
if(L <= l && r <= R && tree[id].mn2 > 0) {
tree[id].mn1 = 0;
return;
}
propagate(id, l, r);
int mid = (l + r) / 2;
maxx(id * 2 + 1, l, mid, L, R);
maxx(id * 2 + 2, mid + 1, r, L, R);
get_value(id);
}
void solve(int id, int l, int r) {
if(l == r) {
ans[l] = tree[id].mx1;
return;
}
propagate(id, l, r);
int mid = (l + r) / 2;
solve(id * 2 + 1, l, mid);
solve(id * 2 + 2, mid + 1, r);
}
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
n = c.size();
q = l.size();
cc = c[0];
for(int i = 0; i < q; i++) {
add(0, 0, n - 1, l[i], r[i], v[i]);
if(v[i] > 0) {
minn(0, 0, n - 1, l[i], r[i]);
}
else {
maxx(0, 0, n - 1, l[i], r[i]);
}
}
ans.resize(n);
solve(0, 0, n - 1);
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
19028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
711 ms |
26900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
19028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
19028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
19028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
