#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N = (int)3e5 + 10;
const ll inf = (ll)1e12;
const ll F = -inf;
bool debug;
struct Node{
ll sigma;
ll set_l;
ll add_l;
int siz;
ll lef_val;
ll rig_val;
int answer;
int ans_pref;
int ans_suff;
};
Node T[N * 4 + 512];
void push(int node, int cl, int cr){
if(T[node].set_l != (ll)1e18){
T[node].sigma = T[node].siz * 1ll * T[node].set_l;
T[node].lef_val = T[node].set_l;
T[node].rig_val = T[node].set_l;
T[node].answer = T[node].siz;
T[node].ans_pref = T[node].siz;
T[node].ans_suff = T[node].siz;
T[node].add_l = 0ll;
if(cl != cr)T[node * 2].set_l = T[node].set_l;
if(cl != cr)T[node * 2 + 1].set_l = T[node].set_l;
T[node].set_l = (ll)1e18;
}
else if(T[node].add_l != 0){
T[node].sigma += T[node].siz * 1ll * T[node].add_l;
T[node].lef_val += T[node].add_l;
T[node].rig_val += T[node].add_l;
if(cl != cr)T[node * 2].add_l += T[node].add_l;
if(cl != cr)T[node * 2 + 1].add_l += T[node].add_l;
T[node].add_l = 0ll;
}
}
Node unite(Node A, Node B){
Node ret;
ret.sigma = A.sigma + B.sigma;
ret.add_l = 0ll;
ret.set_l = (ll)1e18;
ret.siz = A.siz + B.siz;
ret.answer = max(A.answer, B.answer);
ret.lef_val = A.lef_val;
ret.rig_val = B.rig_val;
ret.ans_pref = A.ans_pref;
ret.ans_suff = B.ans_suff;
if(A.rig_val == B.lef_val){
ret.answer = max(ret.answer, A.ans_suff + B.ans_pref);
if(A.ans_pref == A.siz) ret.ans_pref += B.ans_pref;
if(B.ans_suff == B.siz) ret.ans_suff += A.ans_suff;
}
return ret;
}
void upd1(int node, int cl, int cr, int tl, int tr, ll x){
push(node, cl, cr);
if(cr < tl || cl > tr)
return;
if(cl >= tl && cr <= tr){
T[node].set_l = x;
push(node, cl, cr);
return;
}
int mid = (cl + cr) / 2;
upd1(node * 2, cl, mid, tl, tr, x);
upd1(node * 2 + 1, mid + 1, cr, tl, tr, x);
T[node] = unite(T[node * 2], T[node * 2 + 1]);
}
void upd2(int node, int cl, int cr, int tl, int tr, ll x){
push(node, cl, cr);
if(cr < tl || cl > tr)
return;
if(cl >= tl && cr <= tr){
T[node].add_l = x;
push(node, cl, cr);
return;
}
int mid = (cl + cr) / 2;
upd2(node * 2, cl, mid, tl, tr, x);
upd2(node * 2 + 1, mid + 1, cr, tl, tr, x);
T[node] = unite(T[node * 2], T[node * 2 + 1]);
}
ll get_sum(int node, int cl, int cr, int tl, int tr){
push(node, cl, cr);
if(cr < tl || cl > tr)
return 0ll;
if(cl >= tl && cr <= tr){
return T[node].sigma;
}
int mid = (cl + cr) / 2;
return get_sum(node * 2, cl, mid, tl, tr) + get_sum(node * 2 + 1, mid + 1, cr, tl, tr);
}
Node cur;
bool has;
void query(int node, int cl, int cr, int tl, int tr){
push(node, cl, cr);
if(tl > tr) return;
if(cr < tl) return;
if(cl > tr) return;
if(cl >= tl && cr <= tr){
if(!has) {
cur = T[node];
has=true;
}
else{
cur = unite(cur, T[node]);
}
return;
}
int mid = (cl + cr) / 2;
query(node * 2, cl, mid, tl, tr);
query(node * 2 + 1, mid + 1, cr, tl, tr);
}
int n;
ll A[N];
void build(int node, int cl, int cr){
if(cl == cr){
T[node] = {A[cl], (ll)1e18, 0ll,cr-cl+1,A[cl],A[cl],1,1,1};
return;
}
int mid = (cl + cr) / 2;
build(node * 2, cl, mid);
build(node * 2 + 1, mid + 1, cr);
T[node] = unite(T[node * 2], T[node * 2 + 1]);
}
int main(){
fastIO;
freopen("test.txt", "r", stdin);
int q;
cin >> n >> q;
A[0] = F;
for(int i = 1; i <= n; i ++ ){
cin >> A[i];
}
for(int i = n; i >= 1; i -- ){
A[i] = A[i] - A[i - 1];
}
build(1, 0, n);
int type;
ll l, r, s, x;
ll fb, fs;
for(int i = 0 ; i < q; i ++ ){
cin >> type;
if(type == 1){
cin >> l >> r >> s >> x;
if(l + 1 <= r)upd2(1, 0, n, l + 1, r, x);
upd2(1, 0, n, l, l, s);
if(r + 1 <= n)
upd2(1, 0, n, r + 1, r + 1, -(s + (r - l) * 1ll * x));
}
else if(type == 2){
cin >> l >> r >> s >> x;
fb = get_sum(1, 0, n, 0, l - 1);
if(r < n) fs = get_sum(1, 0, n, 0, r + 1);
upd1(1, 0, n, l, l, s - fb);
if(l + 1 <= r)upd1(1, 0, n, l + 1, r, x);
if(r < n) upd1(1, 0, n, r + 1, r + 1, fs-(s+(r-l)*x));
}
else{
cin >> l >> r;
if(l == r){
cout << 1 << "\n";
}
else{
has=false;
query(1, 0, n, l+1, r);
cout << cur.answer + 1 << "\n";
}
}
}
return 0;
}
Compilation message
Progression.cpp: In function 'int main()':
Progression.cpp:155:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
155 | freopen("test.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:184:27: warning: 'fs' may be used uninitialized in this function [-Wmaybe-uninitialized]
184 | if(r < n) upd1(1, 0, n, r + 1, r + 1, fs-(s+(r-l)*x));
| ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
