#include <iostream>
using namespace std;
const int NMAX = 3e5;
int N, Q, d[NMAX + 2];
struct Node
{
bool dummy;
long long sum;
int sz;
int maxPref;
long long valPref;
int maxSuf;
long long valSuf;
int maxProgression;
int lazyType;
long long lazyVal;
Node()
{
dummy = false;
sum = 0LL;
maxPref = 0;
valPref = 0LL;
maxSuf = 0;
valSuf = 0LL;
maxProgression = 0;
lazyType = 0;
lazyVal = 0LL;
}
};
Node Merge(Node A, Node B)
{
if(A.dummy == true)
return B;
if(B.dummy == true)
return A;
Node R;
R.sz = A.sz + B.sz;
R.sum = A.sum + B.sum;
if(A.maxPref == A.sz)
{
if(A.valPref == B.valPref)
{
R.maxPref = A.sz + B.maxPref;
R.valPref = A.valPref;
}
else
{
R.maxPref = A.sz;
R.valPref = A.valPref;
}
}
else
{
R.maxPref = A.maxPref;
R.valPref = A.valPref;
}
if(B.maxSuf == B.sz)
{
if(B.valSuf == A.valSuf)
{
R.maxSuf = B.sz + A.maxSuf;
R.valSuf = B.valSuf;
}
else
{
R.maxSuf = B.sz;
R.valSuf = B.valSuf;
}
}
else
{
R.maxSuf = B.maxSuf;
R.valSuf = B.valSuf;
}
R.maxProgression = max(R.maxPref, R.maxSuf);
R.maxProgression = max(R.maxProgression, A.maxProgression);
R.maxProgression = max(R.maxProgression, B.maxProgression);
if(A.valSuf == B.valPref)
{
R.maxProgression = max(R.maxProgression, A.maxSuf + B.maxPref);
}
return R;
}
struct SegTree
{
Node v[3 * NMAX];
void Build(int node, int st, int dr)
{
if(st == dr)
{
v[node].sz = dr - st + 1;
v[node].sum = v[node].valPref = v[node].valSuf = d[st] - d[st - 1];
v[node].maxPref = v[node].maxSuf = v[node].maxProgression = 1;
return ;
}
int mid = (st + dr) >> 1;
Build(2 * node, st, mid);
Build(2 * node + 1, mid + 1, dr);
v[node] = Merge(v[2 * node], v[2 * node + 1]);
}
/*
void AddPoint(int node, int st, int dr, int pos, long long val) {
}
*/
/*
void SetPoint(int node, int st, int dr, int pos, long long val) {
}
*/
void Propagate(int node, int st, int dr)
{
if(v[node].lazyType == 0)
return ;
int szNode = dr - st + 1;
if(v[node].lazyType == 1)
{
v[node].sum += v[node].lazyVal * szNode;
v[node].valPref += v[node].lazyVal;
v[node].valSuf += v[node].lazyVal;
if(szNode > 1)
{
int mid = (st + dr) >> 1;
if(v[2 * node].lazyType == 2)
{
Propagate(2 * node, st, mid);
}
v[2 * node].lazyType = 1;
v[2 * node].lazyVal += v[node].lazyVal;
if(v[2 * node + 1].lazyType == 2)
{
Propagate(2 * node + 1, mid + 1, dr);
}
v[2 * node + 1].lazyType = 1;
v[2 * node + 1].lazyVal += v[node].lazyVal;
}
}
else
{
v[node].sum = v[node].lazyVal * szNode;
v[node].valPref = v[node].valSuf = v[node].lazyVal;
v[node].maxPref = v[node].maxSuf = v[node].maxProgression = szNode;
if(szNode > 1)
{
v[2 * node].lazyType = 2;
v[2 * node].lazyVal = v[node].lazyVal;
v[2 * node + 1].lazyType = 2;
v[2 * node + 1].lazyVal = v[node].lazyVal;
}
}
v[node].lazyType = 0;
v[node].lazyVal = 0;
}
void AddRange(int node, int st, int dr, int l, int r, long long val)
{
Propagate(node, st, dr);
if(r < st || l > dr)
return ;
if(l <= st && dr <= r)
{
v[node].lazyType = 1;
v[node].lazyVal = val;
Propagate(node, st, dr);
return ;
}
int mid = (st + dr) >> 1;
AddRange(2 * node, st, mid, l, r, val);
AddRange(2 * node + 1, mid + 1, dr, l, r, val);
v[node] = Merge(v[2 * node], v[2 * node + 1]);
}
void SetRange(int node, int st, int dr, int l, int r, long long val)
{
Propagate(node, st, dr);
if(r < st || l > dr)
return ;
if(l <= st && dr <= r)
{
v[node].lazyType = 2;
v[node].lazyVal = val;
Propagate(node, st, dr);
return ;
}
int mid = (st + dr) >> 1;
SetRange(2 * node, st, mid, l, r, val);
SetRange(2 * node + 1, mid + 1, dr, l, r, val);
v[node] = Merge(v[2 * node], v[2 * node + 1]);
}
Node Query(int node, int st, int dr, int l, int r)
{
Propagate(node, st, dr);
if(r < st || l > dr)
{
Node _dummy;
_dummy.dummy = true;
return _dummy;
}
if(l <= st && dr <= r)
return v[node];
int mid = (st + dr) >> 1;
Node a1 = Query(2 * node, st, mid, l, r);
Node a2 = Query(2 * node + 1, mid + 1, dr, l, r);
return Merge(a1, a2);
}
};
SegTree aint;
int main()
{
// The following line disables syncing between cin/scanf and cout/printf.
// It makes input faster, but you must not use functions from <cstdio> (e.g. scanf/printf) directly.
// This line must be executed before any use of cin/cout.
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// Your code goes here ...
// (You can now read input and write output normally using cin/cout.)
cin >> N >> Q;
for(int i = 1; i <= N; i++)
cin >> d[i];
aint.Build(1, 1, N);
for(int i = 1; i <= Q; i++)
{
int typ;
cin >> typ;
if(typ == 1)
{
///patch
int L, R, S, C;
cin >> L >> R >> S >> C;
aint.AddRange(1, 1, N, L, L, S);
if(R + 1 <= N)
aint.AddRange(1, 1, N, R + 1, R + 1, -S - 1LL * (R - L) * C);
if(L + 1 <= R)
aint.AddRange(1, 1, N, L + 1, R, C);
}
else if(typ == 2)
{
///rewrite
int L, R, S, C;
cin >> L >> R >> S >> C;
Node l = aint.Query(1, 1, N, 1, L);
aint.SetRange(1, 1, N, L, L, l.sum - S);
if(R + 1 <= N)
{
Node rr = aint.Query(1, 1, N, 1, R + 1);
aint.SetRange(1, 1, N, R + 1, R + 1, rr.sum - S - 1LL * (R - L) * C);
}
if(L + 1 <= R)
aint.SetRange(1, 1, N, L + 1, R, C);
}
else
{
///evaluate
int L, R;
cin >> L >> R;
if(L == R)
cout << 1 << '\n';
else
{
Node res = aint.Query(1, 1, N, L, R);
if(res.maxProgression != res.sz)
cout << 1 + res.maxProgression << '\n';
else
cout << res.maxProgression << '\n';
}
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
157 ms |
119660 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
56684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
162 ms |
119660 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
159 ms |
119532 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
162 ms |
119660 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
157 ms |
119660 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
