#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define f first
#define s second
#define endl "\n"
const int N = 2e5 + 5, mod = 1e9 + 7, inf = 1e18; //!
int t, d[N], a[N];
struct node {
int L, R, len;
pii suf, pref;
int ans;
} tree[4 * N];
struct z {
int k, b, t;
} lazy[N];
bool eq(int a, int b) {
return (a == -inf || b == -inf ? 1 : a == b);
}
node merge(node a, node b) {
node c;
c.len = a.len + b.len;
c.L = a.L; c.R = b.R;
c.ans = max(a.ans, b.ans);
// cout << eq(a.suf.f, b.suf.f) << endl;
if(eq(a.suf.f, b.pref.f) && eq(a.suf.f, b.L - a.R) && eq(b.pref.f, b.L - a.R)) {
c.ans = max(c.ans, a.suf.s + b.pref.s);
}
if(eq(a.suf.f, b.L - a.R)) {
c.ans = max(c.ans, a.suf.s + 1);
}
if(eq(b.pref.f, b.L - a.R)) {
c.ans = max(c.ans, b.pref.s + 1);
}
c.suf = b.suf;
if(b.suf.s == b.len && eq(a.suf.f, b.pref.f) && eq(a.suf.f, b.L - a.R) && eq(b.suf.f, b.L - a.R)) {
c.suf.s += a.suf.s;
} else if(b.suf.s == b.len && eq(b.suf.f, b.L - a.R)) {
c.suf.s++;
}
c.pref = a.pref;
if(a.pref.s == a.len && eq(a.pref.f, b.pref.f)&& eq(a.pref.f, b.L - a.R) && eq(b.pref.f, b.L - a.R)) {
c.pref.s += b.pref.s;
} else if(a.pref.s == a.len && eq(a.pref.f, b.L - a.R)) c.pref.s++;
if(b.len == 1) {
c.suf.f = b.L - a.R;
}
if(a.len == 1) {
c.pref.f = b.L - a.R;
}
return c;
}
void build(int u,int l,int r) {
if(l == r) {
tree[u].L = tree[u].R = a[l];
tree[u].ans = 1;
tree[u].pref = {-inf, 1};
tree[u].suf = {-inf, 1};
tree[u].len = 1;
return;
}
int mid = (l + r) / 2;
build(2 * u, l, mid); build(2 * u + 1, mid + 1, r);
tree[u] = merge(tree[2 * u], tree[2 * u + 1]);
// cout << l << " " << r << " " << tree[u].ans << " " << tree[u].R << " " << tree[u].suf.f << " " << tree[u].suf.s <<endl;
}
void push(int u,int l,int r) {
if(lazy[u].t) {
tree[u].ans = r - l + 1;
tree[u].L = lazy[u].k * l + lazy[u].b;
tree[u].R = lazy[u].k * r + lazy[u].b;
tree[u].pref.s = tree[u].suf.s = r - l + 1;
tree[u].pref.f = tree[u].suf.f = (r == l ? -inf : lazy[u].k);
tree[u].ans = r - l + 1;
if(l != r) {
lazy[2 * u].t = lazy[2 * u + 1].t = 1;
lazy[2 * u].k = lazy[2 * u + 1].k = lazy[u].k;
lazy[2 * u].b = lazy[2 * u + 1].b = lazy[u].b;
}
} else {
tree[u].L += lazy[u].k * l + lazy[u].b;
tree[u].R += lazy[u].k * r + lazy[u].b;
if(tree[u].len > 0) {
tree[u].pref.f += lazy[u].k;
tree[u].suf.f += lazy[u].k;
}
if(l != r) {
lazy[2 * u].k += lazy[u].k;
lazy[2 * u + 1].k += lazy[u].k;
lazy[2 * u].b += lazy[u].b;
lazy[2 * u + 1].b += lazy[u].b;
}
}
lazy[u].k = lazy[u].b = lazy[u].t = 0;
}
void upd(int u,int st,int en,int l,int r,int k,int b,int t) {
push(u, l, r);
if(l > en || r < st) return;
if(st <= l && r <= en) {
lazy[u].k += k;
lazy[u].b += b;
lazy[u].t = (t == 2);
push(u, l, r);
return;
}
int mid = (l + r) / 2;
upd(2 * u, st, en, l, mid, k, b, t);
upd(2 * u + 1, st, en, mid + 1, r, k, b, t);
tree[u] = merge(tree[2 * u], tree[2 * u + 1]);
}
node get(int u,int st,int en, int l,int r) {
if(st <= l && r <= en) return tree[u];
int mid = (l + r) / 2;
if(mid + 1 > en) return get(2 * u, st, en, l, mid);
if(mid < st) return get(2 * u + 1, st, en, mid + 1, r);
return merge(get(2 * u, st, en, l, mid), get(2 * u + 1, st, en, mid + 1, r));
}
main() {
// ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int n, q;
cin >> n >> q;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
build(1, 1, n);
// ai - a(i - 1) - (a(i - 1) - a(i - 2)) = ai - 2*a(i-1) + a(i-2)
for(int i = 1; i <= q; i++) {
int t;
cin >> t;
if(t < 3) {
int l, r, s, c;
cin >> l >> r >> s >> c;
upd(1, l, r, 1, n, c, s - l * c, t);
continue;
}
int l, r;
cin >> l >> r;
// build(1, 1, n);
cout << get(1, l, r, 1, n).ans << endl;
}
}
Compilation message
Progression.cpp:123:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
123 | main() {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
159 ms |
108264 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
50344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
161 ms |
108368 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
162 ms |
108280 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
161 ms |
108368 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
159 ms |
108264 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
