#include <iostream>
using namespace std;
const int NMAX = 1e5;
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;
bool lfinc, rginc;
int lazyType;
long long lazyVal;
Node()
{
dummy = false;
sum = 0LL;
sz = 0LL;
maxPref = 0;
valPref = 0LL;
maxSuf = 0;
valSuf = 0LL;
maxProgression = 0;
lfinc = rginc = false;
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 = R.maxPref;
R.lfinc = true;
if(R.maxSuf > R.maxProgression)
{
R.maxProgression = R.maxSuf;
R.lfinc = false;
R.rginc = true;
}
if(A.maxProgression > R.maxProgression)
{
R.maxProgression = A.maxProgression;
R.lfinc = false, R.rginc = false;
if(A.lfinc == true) R.lfinc = true;
}
if(B.maxProgression > R.maxProgression)
{
R.maxProgression = B.maxProgression;
R.lfinc = false, R.rginc = false;
if(B.rginc == true) R.rginc = true;
}
if(A.valSuf == B.valPref)
{
if(A.maxSuf + B.maxPref > R.maxProgression)
{
R.maxProgression = A.maxSuf + B.maxPref;
R.lfinc = false;
R.rginc = false;
}
}
if(R.maxProgression == R.sz)
{
R.lfinc = true;
R.rginc = true;
}
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;
v[node].lfinc = v[node].rginc = false;
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;
v[node].lfinc = true;
v[node].rginc = true;
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);
/*
cout << "------------------------\n";
for(int j = 1; j <= N; j++)
cout << aint.Query(1, 1, N, j, j).sum << ' ';
cout << '\n';
cout << "------------------------\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;
long long l = 0;
if(L - 1 >= 1) aint.Query(1, 1, N, 1, L - 1).sum;
aint.SetRange(1, 1, N, L, L, S - l);
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)
{
if(!res.lfinc)
cout << 1 + res.maxProgression << '\n';
else
cout << res.maxProgression << '\n';
}
else
cout << res.maxProgression << '\n';
}
}
/*
cout << "------------------------\n";
for(int j = 1; j <= N; j++)
cout << aint.Query(1, 1, N, j, j).sum << ' ';
cout << '\n';
cout << "------------------------\n";
*/
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
710 ms |
1048576 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
21484 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
21484 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
21996 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
597 ms |
1048580 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
21996 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
710 ms |
1048576 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
