#include <iostream>
using namespace std;
using ll = long long;
#warning change mxn
const int mxn = 3e3+5;
struct Node {
int len = 0;
ll dl = 0, dr = 0;
ll diffl = 0, diffr = 0;
int lenl = 0, lenr = 0, best = 1;
bool set_tag = false;
ll s = 0, c = 0;
};
Node merge(Node lhs, Node rhs) {
Node res{};
res.best = max(lhs.best, rhs.best);
ll diff = rhs.dl-lhs.dr;
res.best = max(res.best, (diff == lhs.diffr ? lhs.lenr : 1)+(diff == rhs.diffl ? rhs.lenl : 1));
if(lhs.len == 1) lhs.diffl = diff, lhs.lenl = 1;
if(rhs.len == 1) rhs.diffr = diff, rhs.lenr = 1;
res.lenl = lhs.lenl + (diff == lhs.diffl && lhs.lenl == lhs.len ? (diff == rhs.diffl ? rhs.lenl : 1) : 0);
res.lenr = rhs.lenr + (diff == rhs.diffr && rhs.lenr == rhs.len ? (diff == lhs.diffr ? lhs.lenr : 1) : 0);
res.best = max(res.best, max(res.lenl, res.lenr));
res.diffl = lhs.diffl, res.diffr = rhs.diffr;
res.dl = lhs.dl, res.dr = rhs.dr;
res.len = lhs.len+rhs.len;
return res;
}
struct Seg {
Node n[4*mxn];
void push(Node &chi, Node par) {
if(par.set_tag) {
chi.dl = par.s, chi.dr = par.s+(chi.len-1)*par.c;
chi.diffl = par.c, chi.diffr = par.c;
chi.lenl = chi.len, chi.lenr = chi.len;
chi.best = chi.len;
chi.set_tag = true;
chi.s = par.s, chi.c = par.c;
}
else {
chi.dl += par.s, chi.dr += par.s+(chi.len-1)*par.c;
chi.diffl += par.c, chi.diffr += par.c;
chi.s += par.s, chi.c += par.c;
}
}
void push(int u) {
Node par = n[u];
push(n[2*u], par);
par.s += n[2*u].len*par.c;
push(n[2*u+1], par);
n[u].set_tag = false;
n[u].s = n[u].c = 0;
}
void pull(int u) {
n[u] = merge(n[2*u], n[2*u+1]);
// printf("merging %d, %d: %d\n", 2*u, 2*u+1, n[u].best);
// printf("%d: len = %d, dl = %lld, dr = %lld, diffl = %lld, diffr = %lld,\nlenl = %d, lenr = %d, best = %d\n",
// 2*u, n[2*u].len, n[2*u].dl, n[2*u].dr, n[2*u].diffl, n[2*u].diffr, n[2*u].lenl, n[2*u].lenr, n[2*u].best);
// printf("%d: len = %d, dl = %lld, dr = %lld, diffl = %lld, diffr = %lld,\nlenl = %d, lenr = %d, best = %d\n",
// 2*u+1, n[2*u+1].len, n[2*u+1].dl, n[2*u+1].dr, n[2*u+1].diffl, n[2*u+1].diffr, n[2*u+1].lenl, n[2*u+1].lenr, n[2*u+1].best);
// printf("----------\n");
}
void add(int u, int l, int r, int ql, int qr, ll s, ll c) {
if(r < ql || l > qr) return;
// printf("add: u = %d, l, r = [%d; %d], ql, qr = [%d; %d], s = %lld, c = %lld,\n", u, l, r, ql, qr, s, c);
if(ql <= l && r <= qr) {
if(l == r) n[u].len = 1;
n[u].s += s, n[u].c += c;
n[u].dl += s, n[u].dr += s+(n[u].len-1)*c;
n[u].diffl += c, n[u].diffr += c;
return;
}
push(u);
int m = (l+r)/2;
add(2*u, l, m, ql, qr, s, c), add(2*u+1, m+1, r, max(m+1, ql), qr, s+max(0, m-ql+1)*c, c);
pull(u);
}
void set(int u, int l, int r, int ql, int qr, ll s, ll c) {
if(r < ql || l > qr) return;
// printf("set: u = %d, l, r = [%d; %d], ql, qr = [%d; %d], s = %lld, c = %lld,\n", u, l, r, ql, qr, s, c);
if(ql <= l && r <= qr) {
if(l == r) n[u].len = 1;
n[u].set_tag = true;
n[u].s = s, n[u].c = c;
n[u].dl = s, n[u].dr = s+(n[u].len-1)*c;
n[u].diffl = c, n[u].diffr = c;
n[u].lenl = n[u].len, n[u].lenr = n[u].len;
n[u].best = n[u].len;
return;
}
push(u);
int m = (l+r)/2;
set(2*u, l, m, ql, qr, s, c), set(2*u+1, m+1, r, max(m+1, ql), qr, s+max(0, m-ql+1)*c, c);
pull(u);
// printf("%d: len = %d, dl = %lld, dr = %lld, diffl = %lld, diffr = %lld,\nlenl = %d, lenr = %d, best = %d\n",
// u, n[u].len, n[u].dl, n[u].dr, n[u].diffl, n[u].diffr, n[u].lenl, n[u].lenr, n[u].best);
}
Node get(int u, int l, int r, int ql, int qr) {
if(r < ql || l > qr) return {};
// printf("get: u = %d, l, r = [%d; %d], ql, qr = [%d; %d]\n", u, l, r, ql, qr);
if(ql <= l && r <= qr) return n[u];
int m = (l+r)/2;
push(u);
Node lhs = get(2*u, l, m, ql, qr);
Node rhs = get(2*u+1, m+1, r, ql, qr);
pull(u);
return (lhs.len == 0 ? rhs : (rhs.len == 0 ? lhs : merge(lhs, rhs)));
}
} seg;
int n, q;
ll D[mxn];
int main() {
cin >> n >> q;
for(int i = 1; i <= n; i++) cin >> D[i];
for(int i = 1; i <= n; i++) {
seg.set(1, 1, n, i, i, D[i], 0);
}
for(int i = 0; i < q; i++) {
ll t, l, r, s, c; cin >> t >> l >> r;
if(t == 1) {
cin >> s >> c;
// for(int j = l; j <= r; j++) D[j] += s+(j-l)*c;
seg.add(1, 1, n, l, r, s, c);
}
else if(t == 2) {
cin >> s >> c;
// for(int j = l; j <= r; j++) D[j] = s+(j-l)*c;
seg.set(1, 1, n, l, r, s, c);
}
else {
// int ans = 1, diff = D[l+1]-D[l], cnt = 1;
// for(int j = l+1; j <= r; j++) {
// if(diff == D[j]-D[j-1]) {
// cnt++; ans = max(ans, cnt);
// }
// else {
// diff = D[j]-D[j-1], cnt = 2;
// }
// }
// cout << ans << "!\n";
cout << seg.get(1, 1, n, l, r).best << "\n";
}
// cerr << "actual:\n";
// for(int i = 1; i <= n; i++) {
// cerr << D[i] << " ";
// }
// cerr << "\n";
// cerr << "got:\n";
// for(int i = 1; i <= n; i++) {
// cerr << seg.get(1, 1, n, i, i).dl << " ";
// }
// cerr << "\n";
}
return 0;
}
Compilation message
Progression.cpp:7:2: warning: #warning change mxn [-Wcpp]
7 | #warning change mxn
| ^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
309 ms |
732 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
340 KB |
Output is correct |
| 2 |
Correct |
3 ms |
212 KB |
Output is correct |
| 3 |
Correct |
2 ms |
212 KB |
Output is correct |
| 4 |
Correct |
2 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
2 ms |
212 KB |
Output is correct |
| 8 |
Correct |
3 ms |
448 KB |
Output is correct |
| 9 |
Correct |
3 ms |
368 KB |
Output is correct |
| 10 |
Correct |
3 ms |
468 KB |
Output is correct |
| 11 |
Correct |
3 ms |
368 KB |
Output is correct |
| 12 |
Correct |
3 ms |
468 KB |
Output is correct |
| 13 |
Correct |
3 ms |
468 KB |
Output is correct |
| 14 |
Correct |
5 ms |
468 KB |
Output is correct |
| 15 |
Correct |
3 ms |
468 KB |
Output is correct |
| 16 |
Correct |
3 ms |
456 KB |
Output is correct |
| 17 |
Correct |
5 ms |
468 KB |
Output is correct |
| 18 |
Correct |
3 ms |
468 KB |
Output is correct |
| 19 |
Correct |
2 ms |
212 KB |
Output is correct |
| 20 |
Correct |
3 ms |
212 KB |
Output is correct |
| 21 |
Correct |
2 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
309 ms |
732 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
