This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int MAX = 300300;
const long long inf = (long long) 1e18;
struct Value {
struct Node {
long long sum;
long long coeff;
long long sum_set;
long long coeff_set;
long long sum_add;
long long coeff_add;
Node(long long _sum = 0, long long _coeff = 0) : sum(_sum), coeff(_coeff) {
sum_set = coeff_set = inf;
sum_add = coeff_add = 0;
}
};
int n;
Node st[8 * MAX];
void Push(int id) {
if (st[id].sum_set == inf) {
st[id * 2].sum += st[id].sum_add;
st[id * 2].coeff += st[id].coeff_add;
st[id * 2 + 1].sum += st[id].sum_add;
st[id * 2 + 1].coeff += st[id].coeff_add;
st[id * 2].sum_add += st[id].sum_add;
st[id * 2].coeff_add += st[id].coeff_add;
st[id * 2 + 1].sum_add += st[id].sum_add;
st[id * 2 + 1].coeff_add += st[id].coeff_add;
st[id].sum_add = 0;
st[id].coeff_add = 0;
} else {
st[id * 2].sum = st[id].sum_set + st[id].sum_add;
st[id * 2].coeff = st[id].coeff_set + st[id].coeff_add;
st[id * 2 + 1].sum = st[id].sum_set + st[id].sum_add;
st[id * 2 + 1].coeff = st[id].coeff_set + st[id].coeff_add;
st[id * 2].sum_set = st[id].sum_set;
st[id * 2].coeff_set = st[id].coeff_set;
st[id * 2].sum_add = st[id].sum_add;
st[id * 2].coeff_add = st[id].coeff_add;
st[id * 2 + 1].sum_set = st[id].sum_set;
st[id * 2 + 1].coeff_set = st[id].coeff_set;
st[id * 2 + 1].sum_add = st[id].sum_add;
st[id * 2 + 1].coeff_add = st[id].coeff_add;
st[id].sum_set = inf;
st[id].coeff_set = inf;
st[id].sum_add = 0;
st[id].coeff_add = 0;
}
}
void Add(int id, int l, int r, int ll, int rr, long long x, long long y) {
if (ll <= l && r <= rr) {
st[id].sum += x;
st[id].coeff += y;
st[id].sum_add += x;
st[id].coeff_add += y;
Push(id);
return;
}
Push(id);
int mid = (l + r) >> 1;
if (rr <= mid) {
Add(id * 2, l, mid, ll, rr, x, y);
} else if (ll > mid) {
Add(id * 2 + 1, mid + 1, r, ll, rr, x, y);
} else {
Add(id * 2, l, mid, ll, rr, x, y);
Add(id * 2 + 1, mid + 1, r, ll, rr, x, y);
}
st[id].sum = st[id * 2].sum + st[id * 2 + 1].sum;
st[id].coeff = st[id * 2].coeff + st[id * 2 + 1].coeff;
}
void Set(int id, int l, int r, int ll, int rr, long long x, long long y) {
if (ll <= l && r <= rr) {
st[id].sum = x;
st[id].coeff = y;
st[id].sum_set = x;
st[id].coeff_set = y;
st[id].sum_add = 0;
st[id].coeff_add = 0;
Push(id);
return;
}
Push(id);
int mid = (l + r) >> 1;
if (rr <= mid) {
Set(id * 2, l, mid, ll, rr, x, y);
} else if (ll > mid) {
Set(id * 2 + 1, mid + 1, r, ll, rr, x, y);
} else {
Set(id * 2, l, mid, ll, rr, x, y);
Set(id * 2 + 1, mid + 1, r, ll, rr, x, y);
}
st[id].sum = st[id * 2].sum + st[id * 2 + 1].sum;
st[id].coeff = st[id * 2].coeff + st[id * 2 + 1].coeff;
}
long long Query(int id, int l, int r, int p) {
if (l == r) {
return st[id].sum + st[id].coeff * p;
}
Push(id);
int mid = (l + r) >> 1;
long long res;
if (p <= mid) {
res = Query(id * 2, l, mid, p);
} else {
res = Query(id * 2 + 1, mid + 1, r, p);
}
st[id].sum = st[id * 2].sum + st[id * 2 + 1].sum;
st[id].coeff = st[id * 2].coeff + st[id * 2 + 1].coeff;
return res;
}
long long Get(int i) {
return Query(1, 0, n - 1, i);
}
} val;
struct Solver {
struct Node {
int len;
int mx;
int mx_l;
int mx_r;
long long val_l;
long long val_r;
long long lzy_add;
long long lzy_set;
Node() {
lzy_set = inf;
lzy_add = 0;
}
};
Node Merge(Node a, Node b) {
Node nd;
nd.len = a.len + b.len;
nd.mx = max(a.mx, b.mx);
nd.mx_l = a.mx_l;
nd.mx_r = b.mx_r;
if (a.val_r == b.val_l) {
nd.mx = max(nd.mx, a.mx_r + b.mx_l);
if (a.mx_l == a.len) {
nd.mx_l = max(nd.mx_l, a.len + b.mx_l);
}
if (b.mx_r == b.len) {
nd.mx_r = max(nd.mx_r, a.mx_r + b.len);
}
}
nd.val_l = a.val_l;
nd.val_r = b.val_r;
return nd;
}
Node st[8 * MAX];
void Push(int id) {
if (st[id].lzy_set == inf) {
st[id * 2].val_l += st[id].lzy_add;
st[id * 2].val_r += st[id].lzy_add;
st[id * 2 + 1].val_l += st[id].lzy_add;
st[id * 2 + 1].val_r += st[id].lzy_add;
st[id * 2].lzy_add += st[id].lzy_add;
st[id * 2 + 1].lzy_add += st[id].lzy_add;
st[id].lzy_add = 0;
} else {
st[id * 2].val_l = st[id].lzy_set + st[id].lzy_add;
st[id * 2].val_r = st[id].lzy_set + st[id].lzy_add;
st[id * 2 + 1].val_l = st[id].lzy_set + st[id].lzy_add;
st[id * 2 + 1].val_r = st[id].lzy_set + st[id].lzy_add;
st[id * 2].lzy_set = st[id].lzy_set;
st[id * 2].lzy_add = st[id].lzy_add;
st[id * 2 + 1].lzy_set = st[id].lzy_set;
st[id * 2 + 1].lzy_add = st[id].lzy_add;
st[id * 2].mx = st[id * 2].mx_l = st[id * 2].mx_r = st[id * 2].len;
st[id * 2 + 1].mx = st[id * 2 + 1].mx_l = st[id * 2 + 1].mx_r = st[id * 2 + 1].len;
st[id].lzy_set = inf;
st[id].lzy_add = 0;
}
}
void Build(int id, int l, int r) {
if (l == r) {
st[id].val_l = st[id].val_r = 0;
st[id].len = 1;
st[id].mx = st[id].mx_l = st[id].mx_r = 1;
return;
}
int mid = (l + r) >> 1;
Build(id * 2, l, mid);
Build(id * 2 + 1, mid + 1, r);
st[id] = Merge(st[id * 2], st[id * 2 + 1]);
}
void Set(int id, int l, int r, int ll, int rr, long long x) {
if (ll <= l && r <= rr) {
st[id].mx = st[id].mx_l = st[id].mx_r = st[id].len;
st[id].val_l = x;
st[id].val_r = x;
st[id].lzy_set = x;
st[id].lzy_add = 0;
Push(id);
return;
}
Push(id);
int mid = (l + r) >> 1;
if (rr <= mid) {
Set(id * 2, l, mid, ll, rr, x);
} else if (ll > mid) {
Set(id * 2 + 1, mid + 1, r, ll, rr, x);
} else {
Set(id * 2, l, mid, ll, rr, x);
Set(id * 2 + 1, mid + 1, r, ll, rr, x);
}
st[id] = Merge(st[id * 2], st[id * 2 + 1]);
}
void Add(int id, int l, int r, int ll, int rr, long long x) {
if (ll <= l && r <= rr) {
st[id].val_l += x;
st[id].val_r += x;
st[id].lzy_add += x;
Push(id);
return;
}
Push(id);
int mid = (l + r) >> 1;
if (rr <= mid) {
Add(id * 2, l, mid, ll, rr, x);
} else if (ll > mid) {
Add(id * 2 + 1, mid + 1, r, ll, rr, x);
} else {
Add(id * 2, l, mid, ll, rr, x);
Add(id * 2 + 1, mid + 1, r, ll, rr, x);
}
st[id] = Merge(st[id * 2], st[id * 2 + 1]);
}
Node Query(int id, int l, int r, int ll, int rr) {
if (ll <= l && r <= rr) {
return st[id];
}
Push(id);
int mid = (l + r) >> 1;
Node ret;
if (rr <= mid) {
ret = Query(id * 2, l, mid, ll, rr);
} else if (ll > mid) {
ret = Query(id * 2 + 1, mid + 1, r, ll, rr);
} else {
ret = Merge(Query(id * 2, l, mid, ll, rr), Query(id * 2 + 1, mid + 1, r, ll, rr));
}
st[id] = Merge(st[id * 2], st[id * 2 + 1]);
return ret;
}
} st;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, q;
cin >> n >> q;
for (int i = 0; i < n; i++) {
int d;
cin >> d;
val.Set(1, 0, n - 1, i, i, d, 0);
}
val.n = n;
st.Build(1, 0, n - 1);
for (int i = 0; i + 1 < n; i++) {
st.Set(1, 0, n - 1, i, i, val.Get(i) - val.Get(i + 1));
}
while (q--) {
int op;
cin >> op;
if (op == 1) {
int l, r, s, c;
cin >> l >> r >> s >> c;
--l; --r;
val.Add(1, 0, n - 1, l, r, s - c * 1LL * l, c);
if (l < r) {
st.Add(1, 0, n - 1, l, r - 1, -c);
}
if (l > 0) {
st.Set(1, 0, n - 1, l - 1, l - 1, val.Get(l - 1) - val.Get(l));
}
if (r + 1 < n) {
st.Set(1, 0, n - 1, r, r, val.Get(r) - val.Get(r + 1));
}
}
if (op == 2) {
int l, r, s, c;
cin >> l >> r >> s >> c;
--l; --r;
val.Set(1, 0, n - 1, l, r, s - c * 1LL * l, c);
if (l < r) {
st.Set(1, 0, n - 1, l, r - 1, -c);
}
if (l > 0) {
st.Set(1, 0, n - 1, l - 1, l - 1, val.Get(l - 1) - val.Get(l));
}
if (r + 1 < n) {
st.Set(1, 0, n - 1, r, r, val.Get(r) - val.Get(r + 1));
}
}
if (op == 3) {
int l, r;
cin >> l >> r;
--l; --r;
if (l == r) {
cout << 1 << '\n';
} else {
cout << st.Query(1, 0, n - 1, l, r - 1).mx + 1 << '\n';
}
}
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |