#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int) x.size())
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x, y) cerr << #x << " is " << x << ", " << #y << " is " << y << endl;
#define show3(x, y, z) cerr << #x << " is " << x << ", " << #y << " is " << y << ", " << #z << " is " << z << endl;
typedef long long lint;
typedef pair<lint, lint> ii;
struct thing{
lint leftval, rightval, leftcnt, rightcnt, best, full;
};
inline thing single(int u){
return {u,u,1,1,1,1};
}
inline thing merge(thing L, thing R){
thing res;
if(L.full and R.full and L.rightval == R.leftval){
return {L.leftval, R.rightval, L.leftcnt+R.leftcnt, L.rightcnt+R.rightcnt, L.best+R.best, 1};
}
res.leftval = L.leftval, res.rightval = R.rightval;
res.leftcnt = L.leftcnt, res.rightcnt = R.rightcnt;
res.best = max(L.best, R.best);
res.full = 0;
if(L.rightval == R.leftval){
res.best = max(res.best, L.rightcnt + R.leftcnt);
if(L.full) res.leftcnt += R.leftcnt;
else if(R.full) res.rightcnt += L.rightcnt;
res.best = max(res.best, res.leftcnt);
res.best = max(res.best, res.rightcnt);
}
return res;
}
lint arr[300005];
struct node{
int s, e, m;
thing val;
lint add = 0;
node *l, *r;
node(int S, int E){
s = S, e = E, m = (s+e)/2;
if(s == e) val = single(arr[s]);
else{
l = new node(s,m);
r = new node(m+1,e);
val = merge(l->val, r->val);
add = 0;
}
}
void applyadd(lint A){
val.leftval += A;
val.rightval += A;
add += A;
}
void push(){
if(add != 0 and s != e){
l->applyadd(add);
r->applyadd(add);
add = 0;
}
}
thing query(int S, int E){
push();
if(s == S and E == e) return val;
else if(E <= m) return l->query(S,E);
else if(S >= m+1) return r->query(S,E);
else return merge(l->query(S,m), r->query(m+1,E));
}
void updateadd(int S, int E, lint A){
push();
if(s == S and E == e){
applyadd(A);
push();
}
else{
if(E <= m) l->updateadd(S,E,A);
else if(S >= m+1) r->updateadd(S,E,A);
else l->updateadd(S,m,A), r->updateadd(m+1,E,A);
val = merge(l->val, r->val);
}
}
} *root;
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
freopen("i.txt","r",stdin);
int n, Q; cin >> n >> Q;
lint x; cin >> x;
for(int i = 2;i <= n;i++){
lint y; cin >> y;
arr[i-1] = y-x;
x = y;
}
if(n != 1) root = new node(1,n-1);
while(Q--){
lint t, l, r; cin >> t >> l >> r;
if(t == 3){
if(l == r) cout << "1\n";
else cout << root->query(l,r-1).best+1 << '\n';
}
else{
lint a, b; cin >> a >> b;
if(n == 1) continue;
if(t == 1){
if(l != r) root->updateadd(l,r-1,b);
if(l != 1) root->updateadd(l-1,l-1,a);
if(r != n) root->updateadd(r,r,-((r-l)*b+a));
}
}
}
}
Compilation message
Progression.cpp: In function 'int main()':
Progression.cpp:99:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
99 | freopen("i.txt","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
1228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
1228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
1228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
1152 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
1228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
1228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
