#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define tpip tuple<pii, int, pii>
using namespace std;
struct node{
int s, e, m, sum, maxcos, lazyset, lazyadd;
pii pref, suff;
node *l, *r;
node(int _s, int _e): s(_s), e(_e), m((_s+_e)/2), maxcos(0), lazyset(-1), lazyadd(0){
if (s != e){
l = new node(s, m);
r = new node(m+1, e);
}
}
void value(){
if (lazyset != -1){
pref = suff = pii(lazyset+lazyadd, e-s+1);
sum = (lazyset + lazyadd) * (e-s+1);
if (s!=e){
l->lazyset = r->lazyset = lazyset;
l->lazyadd = r->lazyadd = lazyadd;
}
lazyadd = 0;
lazyset = -1;
maxcos = e - s + 1;
} else {
pref.first += lazyadd;
suff.first += lazyadd;
sum += lazyadd * (e-s+1);
if (s != e){
l->lazyadd += lazyadd;
r->lazyadd += lazyadd;
}
lazyadd = 0;
}
}
tpip merge_child(tpip lft, tpip rgt, bool upd = true){
if (s==e) return tpip(pref, maxcos, suff);
pii pref, suff;
int maxcos = 2;
auto [lpref, lmaxcos, lsuff] = lft;
auto [rpref, rmaxcos, rsuff] = rgt;
if (lpref == lsuff && lpref.first == rpref.first){
pref = pii(lpref.first, lpref.second + rpref.second);
} else {
pref = lpref;
}
if (rpref == rsuff && lsuff.first == rpref.first){
suff = pii(lsuff.first, lsuff.second + rpref.second);
} else {
suff = rsuff;
}
if (lsuff.first == rpref.first){
maxcos = lsuff.second + rpref.second;
}
maxcos = max({maxcos, pref.second, suff.second, lmaxcos, rmaxcos});
if (upd){
this->pref = pref;
this->suff = suff;
this->maxcos = maxcos;
}
return tpip(pref, maxcos, suff);
}
void add(int x, int y, int val){
value();
if (s==x && e==y){
lazyadd += val;
return;
}
if (y <= m) l->add(x, y, val);
else if (x > m) r->add(x, y, val);
else l->add(x, m, val), r->add(m+1, y, val);
l->value(); r->value();
tpip lft = tpip(l->pref, l->maxcos, l->suff);
tpip rgt = tpip(r->pref, r->maxcos, r->suff);
merge_child(lft, rgt);
sum = l->sum + r->sum;
}
void set(int x, int y, int val){
value();
if (s==x && e==y){
lazyset = val;
return;
}
if (y <= m) l->set(x, y, val);
else if (x > m) r->set(x, y, val);
else l->set(x, m, val), r->set(m+1, y, val);
l->value(); r->value();
tpip lft = tpip(l->pref, l->maxcos, l->suff);
tpip rgt = tpip(r->pref, r->maxcos, r->suff);
merge_child(lft, rgt);
sum = l->sum + r->sum;
}
tpip query(int x, int y){
value();
if (s==x && e==y){
return tpip(pref, maxcos, suff);
}
if (y <= m) return l->query(x, y);
else if (x > m) return r->query(x, y);
else {
tpip lft = l->query(x, m);
tpip rgt = r->query(m+1, y);
tpip ans = merge_child(lft, rgt, false);
return ans;
}
}
int maxplayable(int x, int y){
tpip ans = query(x, y);
return get<1>(ans);
}
int range_sum(int x, int y){
value();
if (s==x && e==y) return sum;
else if (y <= m) return l->range_sum(x, y);
else if (x > m) return r->range_sum(x, y);
else return l->range_sum(x, m) + r->range_sum(m+1, y);
}
} *root;
main(){
int n, q; cin >> n >> q;
int st; cin >> st;
int pref = st;
root = new node(0, n-2);
for (int i = 0; i < n - 1; i++){
int g; cin >> g;
root->set(i, i, g-pref);
pref = g;
}
for (int i = 0; i < q; i++){
int t; cin >> t;
if (t==3){
int a, b; cin >> a >> b; a--; b--;
if (a == b) cout << "1\n";
else cout << root->maxplayable(a, b-1) + 1 << '\n';
} else if (t==2){
int l, r, s, c; cin >> l >> r >> s >> c;
l--; r--;
int prev = -1, aft = -1;
if (l == 0) st = s;
else if (l==1) prev = st;
else prev = st + root->range_sum(0, l-2);
if (r!=n-1) aft = st + root->range_sum(0, r);
int e = s + (r-l) * c;
if (prev != -1) root->set(l-1, l-1, s-prev);
if (aft != -1) root->set(r, r, aft-e);
if (l != r) root->set(l, r-1, c);
} else {
int l, r, s, c; cin >> l >> r >> s >> c;
l--; r--;
if (l == 0) st += s;
else root->add(l-1, l-1, s);
if (r != n-1) root->add(r, r, -(s + (r-l)*c));
if (l != r) root->add(l, r-1, c);
}
/*
for (int i = 0; i < n; i++){
if (i==0) cout << st << ' ';
else cout << st + root->range_sum(0, i-1) << ' ';
}
cout << endl;
*/
}
}
Compilation message
Progression.cpp:121:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
121 | main(){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1004 ms |
66796 KB |
Output is correct |
| 2 |
Incorrect |
514 ms |
620 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1659 ms |
67180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2051 ms |
68936 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1659 ms |
67180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1004 ms |
66796 KB |
Output is correct |
| 2 |
Incorrect |
514 ms |
620 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
