#include <bits/stdc++.h>
using namespace std;
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("%d %d:\n", lo, hi);
REP (i, 0, 4) {
v[u][i] = cap;
debug(" %d: %lld %lld %d %d\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("%d %d:\n", lo, hi);
REP (i, 0, 4) {
debug(" %d: %lld %lld %d %d\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);
}
}
int main() {
scanf("%d%d", &n, &q);
init();
REP (i, 1, n + 1) {
int d; scanf("%d", &d);
upset(i, i, d, 0);
}
while (q--) {
int t; scanf("%d", &t);
if (t == 1) {
int l, r, s, c; scanf("%d%d%d%d", &l, &r, &s, &c);
incre(l, r, s, c);
} else if (t == 2) {
int l, r, s, c; scanf("%d%d%d%d", &l, &r, &s, &c);
upset(l, r, s, c);
} else {
int l, r; scanf("%d%d", &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);
printf("%d: %lld %d %d\n", id, res[id].c, res[id].s, res[id].e);
printf("%d\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(int, int, int)':
Progression.cpp:59:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
59 | #define MLR int mid = lo + hi >> 1; int lc = u << 1, rc = u << 1 ^ 1
| ~~~^~~~
Progression.cpp:65:2: note: in expansion of macro 'MLR'
65 | MLR;
| ^~~
Progression.cpp: In function 'void init(int, int, int)':
Progression.cpp:59:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
59 | #define MLR int mid = lo + hi >> 1; int lc = u << 1, rc = u << 1 ^ 1
| ~~~^~~~
Progression.cpp:146:3: note: in expansion of macro 'MLR'
146 | MLR;
| ^~~
Progression.cpp: In function 'void upset(int, int, int, int, int, int, int)':
Progression.cpp:59:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
59 | #define MLR int mid = lo + hi >> 1; int lc = u << 1, rc = u << 1 ^ 1
| ~~~^~~~
Progression.cpp:167:2: note: in expansion of macro 'MLR'
167 | MLR;
| ^~~
Progression.cpp: In function 'void incre(int, int, int, int, int, int, int)':
Progression.cpp:59:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
59 | #define MLR int mid = lo + hi >> 1; int lc = u << 1, rc = u << 1 ^ 1
| ~~~^~~~
Progression.cpp:193:2: note: in expansion of macro 'MLR'
193 | MLR;
| ^~~
Progression.cpp: In function 'void query(int, int, int, int, int)':
Progression.cpp:59:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
59 | #define MLR int mid = lo + hi >> 1; int lc = u << 1, rc = u << 1 ^ 1
| ~~~^~~~
Progression.cpp:211:2: note: in expansion of macro 'MLR'
211 | MLR;
| ^~~
Progression.cpp: In function 'int main()':
Progression.cpp:234:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
234 | scanf("%d%d", &n, &q);
| ~~~~~^~~~~~~~~~~~~~~~
Progression.cpp:237:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
237 | int d; scanf("%d", &d);
| ~~~~~^~~~~~~~~~
Progression.cpp:241:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
241 | int t; scanf("%d", &t);
| ~~~~~^~~~~~~~~~
Progression.cpp:243:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
243 | int l, r, s, c; scanf("%d%d%d%d", &l, &r, &s, &c);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:246:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
246 | int l, r, s, c; scanf("%d%d%d%d", &l, &r, &s, &c);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:249:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
249 | int l, r; scanf("%d%d", &l, &r);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
678 ms |
151408 KB |
Output isn't correct |
| 2 |
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 |
1004 ms |
155972 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1326 ms |
150840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1004 ms |
155972 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
678 ms |
151408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
