#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(int 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;
}
};
#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(-INF); ladd[u].reset(0);
}
ap join(ap& l, ap& r) {
ap res;
res.reset(0);
if (l.m == r.m && l.c == r.c && l.e + 1 == r.s) {
res = {l.m, l.c, l.s, r.e};
}
return res;
}
void merge(ap* res, ap* lft, ap* rht) {
res[0] = max(lft[0], lft[2]);
res[1] = max(rht[1], rht[2]);
res[3] = max(lft[3], max(rht[3], max(lft[1],
max(rht[0], join(lft[1], rht[0])))));
res[2] = join(lft[2], rht[2]);
}
void init(int u = 1, int lo = 1, int hi = n) {
lset[u].reset(-INF); ladd[u].reset(0);
REP (i, 0, 4) {
v[u][i].s = lo;
v[u][i].e = hi;
}
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};
lset[u] = cap;
ladd[u].reset(0);
REP (i, 0, 4) {
if (i == 2) {
v[u][i] = cap;
} else {
v[u][i].reset(0);
}
}
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]);
}
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};
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;
REP (i, 0, 4) {
mxto(ans, res[i].e - res[i].s + 1);
}
printf("%d\n", ans);
}
}
return 0;
}
Compilation message
Progression.cpp: In function 'void propo(int, int, int)':
Progression.cpp:56:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
56 | #define MLR int mid = lo + hi >> 1; int lc = u << 1, rc = u << 1 ^ 1
| ~~~^~~~
Progression.cpp:62:2: note: in expansion of macro 'MLR'
62 | MLR;
| ^~~
Progression.cpp: In function 'void init(int, int, int)':
Progression.cpp:56:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
56 | #define MLR int mid = lo + hi >> 1; int lc = u << 1, rc = u << 1 ^ 1
| ~~~^~~~
Progression.cpp:112:3: note: in expansion of macro 'MLR'
112 | MLR;
| ^~~
Progression.cpp: In function 'void upset(int, int, int, int, int, int, int)':
Progression.cpp:56:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
56 | #define MLR int mid = lo + hi >> 1; int lc = u << 1, rc = u << 1 ^ 1
| ~~~^~~~
Progression.cpp:132:2: note: in expansion of macro 'MLR'
132 | MLR;
| ^~~
Progression.cpp: In function 'void incre(int, int, int, int, int, int, int)':
Progression.cpp:56:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
56 | #define MLR int mid = lo + hi >> 1; int lc = u << 1, rc = u << 1 ^ 1
| ~~~^~~~
Progression.cpp:151:2: note: in expansion of macro 'MLR'
151 | MLR;
| ^~~
Progression.cpp: In function 'void query(int, int, int, int, int)':
Progression.cpp:56:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
56 | #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 'int main()':
Progression.cpp:192:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
192 | scanf("%d%d", &n, &q);
| ~~~~~^~~~~~~~~~~~~~~~
Progression.cpp:195:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
195 | int d; scanf("%d", &d);
| ~~~~~^~~~~~~~~~
Progression.cpp:199:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
199 | int t; scanf("%d", &t);
| ~~~~~^~~~~~~~~~
Progression.cpp:201:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
201 | int l, r, s, c; scanf("%d%d%d%d", &l, &r, &s, &c);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:204:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
204 | int l, r, s, c; scanf("%d%d%d%d", &l, &r, &s, &c);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:207:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
207 | int l, r; scanf("%d%d", &l, &r);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
464 ms |
156800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
839 ms |
155160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1107 ms |
158020 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
839 ms |
155160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
464 ms |
156800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
