#include <bits/stdc++.h>
using namespace std;
#define int ll
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
#ifdef DEBUG
#define debug(args...) printf(args)
#else
#define debug(args...)
#endif
#define INF 1000000005
#define LINF 1000000000000000005
#define MOD 1000000007
#define MAXN 300005
int n, q;
struct ap {
ll m, c;
int s, e;
void reset(ll x) {
m = c = x;
s = -1;
e = -10;
}
bool operator< (const ap &o) const {
return e - s < o.e - o.s;
}
ap& operator+= (const ap &o) {
this -> m += o.m;
this -> c += o.c;
return *this;
}
ll eval(ll x) {
return m * x + c;
}
};
#define MLR int mid = lo + hi >> 1; int lc = u << 1, rc = u << 1 ^ 1
ap v[MAXN * 4][4]; // 0 is left, 1 is right, 2 is both, 3 is middle
ap lset[MAXN * 4], ladd[MAXN * 4];
void propo(int u, int lo, int hi) {
if (lo == hi) return;
MLR;
if (lset[u].m != -LINF) {
lset[lc].m = lset[u].m;
lset[lc].c = lset[u].c;
lset[rc].m = lset[u].m;
lset[rc].c = lset[u].c;
REP (i, 0, 4) {
if (i == 2) {
v[lc][i] = {lset[u].m, lset[u].c, lo, mid};
v[rc][i] = {lset[u].m, lset[u].c, mid + 1, hi};
} else {
v[lc][i].reset(0);
v[rc][i].reset(0);
}
}
}
if (ladd[u].m != 0 || ladd[u].c != 0) {
ladd[lc] += ladd[u];
ladd[rc] += ladd[u];
REP (i, 0, 4) {
v[lc][i] += ladd[u];
v[rc][i] += ladd[u];
}
}
lset[u].reset(-LINF); ladd[u].reset(0);
}
ap join(ap l, ap r, int hlf) {
ap res;
res.reset(0);
if (l.e + 1 != r.s) return res;
if (l.e == l.s && r.e == r.s) {
ll m = r.c - l.c;
// l.c = m(l.s) + c
ll c = l.c - m * l.s;
l.m = r.m = m;
l.c = r.c = c;
} else if (l.e == l.s) {
ll ex = r.eval(r.s - 1);
if (l.c == ex) {
l.m = r.m;
l.c = r.c;
}
} else if (r.e == r.s) {
ll ex = l.eval(l.e + 1);
if (r.c == ex) {
r.m = l.m;
r.c = l.c;
}
}
if (l.m == r.m && l.c == r.c) {
res = {l.m, l.c, l.s, r.e};
}
if (hlf & 1) {
ll ex = r.eval(r.s - 1);
if (l.eval(r.s - 1) == ex) {
mxto(res, {r.m, r.c, r.s - 1, r.e});
}
}
if (hlf & 2) {
ll ex = l.eval(l.e + 1);
if (r.eval(l.e + 1) == ex) {
mxto(res, {l.m, l.c, l.s, l.e + 1});
}
}
return res;
}
void merge(ap* res, ap* lft, ap* rht) {
res[0] = max(lft[0], max(lft[2], join(lft[2], rht[0], 2)));
res[1] = max(rht[1], max(rht[2], join(lft[1], rht[2], 1)));
res[3] = max(lft[3], max(rht[3], max(lft[1],
max(rht[0], join(lft[1], rht[0], 3)))));
res[2] = join(lft[2], rht[2], 0);
}
void init(int u = 1, int lo = 1, int hi = n) {
lset[u].reset(-LINF); ladd[u].reset(0);
REP (i, 0, 4) {
v[u][i].reset(0);
}
if (lo != hi) {
MLR;
init(lc, lo, mid);
init(rc, mid + 1, hi);
}
}
void upset(int s, int e, int c, int m, int u = 1, int lo = 1, int hi = n) {
if (lo >= s && hi <= e) {
ap cap = {m, c - m * (s - 1), lo, hi};
if (s == e) {
cap = {0, c, lo, hi};
}
lset[u] = cap;
ladd[u].reset(0);
debug("%lld %lld:\n", lo, hi);
REP (i, 0, 4) {
v[u][i] = cap;
debug(" %lld: %lld %lld %lld %lld\n", i, v[u][i].m, v[u][i].c, v[u][i].s, v[u][i].e);
}
return;
}
propo(u, lo, hi);
MLR;
if (s <= mid) {
upset(s, e, c, m, lc, lo, mid);
}
if (e > mid) {
upset(s, e, c, m, rc, mid + 1, hi);
}
merge(v[u], v[lc], v[rc]);
debug("%lld %lld:\n", lo, hi);
REP (i, 0, 4) {
debug(" %lld: %lld %lld %lld %lld\n", i, v[u][i].m, v[u][i].c, v[u][i].s, v[u][i].e);
}
}
void incre(int s, int e, int c, int m, int u = 1, int lo = 1, int hi = n) {
if (lo >= s && hi <= e) {
ap cap = {m, c - m * (s - 1), lo, hi};
if (s == e) {
cap = {0, c, lo, hi};
}
ladd[u] += cap;
REP (i, 0, 4) {
v[u][i] += cap;
}
return;
}
propo(u, lo, hi);
MLR;
if (s <= mid) {
incre(s, e, c, m, lc, lo, mid);
}
if (e > mid) {
incre(s, e, c, m, rc, mid + 1, hi);
}
merge(v[u], v[lc], v[rc]);
}
ap res[4];
void query(int s, int e, int u = 1, int lo = 1, int hi = n) {
if (lo >= s && hi <= e) {
REP (i, 0, 4) {
res[i] = v[u][i];
}
return;
}
propo(u, lo, hi);
MLR;
if (e <= mid) {
query(s, e, lc, lo, mid);
return;
} else if (s > mid) {
query(s, e, rc, mid + 1, hi);
return;
} else {
query(s, e, lc, lo, mid);
ap lft[4];
REP (i, 0, 4) {
lft[i] = res[i];
}
query(s, e, rc, mid + 1, hi);
ap rht[4];
REP (i, 0, 4) {
rht[i] = res[i];
}
merge(res, lft, rht);
}
}
main() {
scanf("%lld%lld", &n, &q);
init();
REP (i, 1, n + 1) {
int d; scanf("%lld", &d);
upset(i, i, d, 0);
}
while (q--) {
int t; scanf("%lld", &t);
if (t == 1) {
int l, r, s, c; scanf("%lld%lld%lld%lld", &l, &r, &s, &c);
incre(l, r, s, c);
} else if (t == 2) {
int l, r, s, c; scanf("%lld%lld%lld%lld", &l, &r, &s, &c);
upset(l, r, s, c);
} else {
int l, r; scanf("%lld%lld", &l, &r);
query(l, r);
int ans = 0;
int id = -1;
REP (i, 0, 4) {
if (mxto(ans, res[i].e - res[i].s + 1)) {
id = i;
}
}
assert(id != -1);
debug("%lld: %lld %lld %lld\n", id, res[id].c, res[id].s, res[id].e);
printf("%lld\n", ans);
}
}
return 0;
}
/*
10 6
1 2 3 4 1 2 3 4 5 5
3 1 10
1 1 4 -1 -1
3 1 10
3 9 10
2 5 10 -2 -2
3 1 10
10 1
1 2 3 4 1 2 3 4 5 5
3 1 10
10 1
0 0 0 0 -2 -4 -6 -8 -10 -12
3 1 10
*/
Compilation message
Progression.cpp: In function 'void propo(ll, ll, ll)':
Progression.cpp:61:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
61 | #define MLR int mid = lo + hi >> 1; int lc = u << 1, rc = u << 1 ^ 1
| ~~~^~~~
Progression.cpp:67:2: note: in expansion of macro 'MLR'
67 | MLR;
| ^~~
Progression.cpp: In function 'void init(ll, ll, ll)':
Progression.cpp:61:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
61 | #define MLR int mid = lo + hi >> 1; int lc = u << 1, rc = u << 1 ^ 1
| ~~~^~~~
Progression.cpp:148:3: note: in expansion of macro 'MLR'
148 | MLR;
| ^~~
Progression.cpp: In function 'void upset(ll, ll, ll, ll, ll, ll, ll)':
Progression.cpp:61:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
61 | #define MLR int mid = lo + hi >> 1; int lc = u << 1, rc = u << 1 ^ 1
| ~~~^~~~
Progression.cpp:169:2: note: in expansion of macro 'MLR'
169 | MLR;
| ^~~
Progression.cpp: In function 'void incre(ll, ll, ll, ll, ll, ll, ll)':
Progression.cpp:61:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
61 | #define MLR int mid = lo + hi >> 1; int lc = u << 1, rc = u << 1 ^ 1
| ~~~^~~~
Progression.cpp:195:2: note: in expansion of macro 'MLR'
195 | MLR;
| ^~~
Progression.cpp: In function 'void query(ll, ll, ll, ll, ll)':
Progression.cpp:61:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
61 | #define MLR int mid = lo + hi >> 1; int lc = u << 1, rc = u << 1 ^ 1
| ~~~^~~~
Progression.cpp:213:2: note: in expansion of macro 'MLR'
213 | MLR;
| ^~~
Progression.cpp: At global scope:
Progression.cpp:235:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
235 | main() {
| ^~~~
Progression.cpp: In function 'int main()':
Progression.cpp:236:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
236 | scanf("%lld%lld", &n, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
Progression.cpp:239:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
239 | int d; scanf("%lld", &d);
| ~~~~~^~~~~~~~~~~~
Progression.cpp:243:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
243 | int t; scanf("%lld", &t);
| ~~~~~^~~~~~~~~~~~
Progression.cpp:245:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
245 | int l, r, s, c; scanf("%lld%lld%lld%lld", &l, &r, &s, &c);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:248:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
248 | int l, r, s, c; scanf("%lld%lld%lld%lld", &l, &r, &s, &c);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:251:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
251 | int l, r; scanf("%lld%lld", &l, &r);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
590 ms |
197956 KB |
Output is correct |
| 2 |
Correct |
124 ms |
644 KB |
Output is correct |
| 3 |
Correct |
126 ms |
580 KB |
Output is correct |
| 4 |
Correct |
121 ms |
488 KB |
Output is correct |
| 5 |
Incorrect |
121 ms |
712 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
882 ms |
198328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1358 ms |
197684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
882 ms |
198328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
590 ms |
197956 KB |
Output is correct |
| 2 |
Correct |
124 ms |
644 KB |
Output is correct |
| 3 |
Correct |
126 ms |
580 KB |
Output is correct |
| 4 |
Correct |
121 ms |
488 KB |
Output is correct |
| 5 |
Incorrect |
121 ms |
712 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
