/**
____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|
**/
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int maxn = 3e5 + 10;
int n, q;
ll d[maxn], b[maxn];
void input()
{
cin >> n >> q;
for (int i = 1; i <= n; i ++)
{
cin >> d[i];
b[i] = d[i] - d[i - 1];
}
}
int query(int l, int r)
{
if (l == r)
return 1;
int cnt = 1, mx = 0;
for (int i = l + 2; i <= r; i ++)
{
if (b[i] == b[i -1])
cnt ++;
else
{
if (cnt > mx)
mx = cnt;
cnt = 1;
}
}
if (cnt > mx)
mx = cnt;
return mx + 1;
}
const ll inf = 1e18;
struct line
{
ll k, m;
line(ll _k = 0, ll _m = -inf)
{
k = _k;
m = _m;
}
ll math(ll x)
{
return k * x + m;
}
void add_line(line cur)
{
k += cur.k;
m += cur.m;
}
void set_line(line cur)
{
k = cur.k;
m = cur.m;
}
};
line set_lazy[4 * maxn], add_lazy[4 * maxn];
int set_tag[4 * maxn], add_tag[4 * maxn];
void push_lazy(int root, int left, int right)
{
int mid = (left + right) / 2;
if (set_tag[root] == 1)
{
///li_chao[root].set_line(set_lazy[root]);
if (left != right)
{
set_tag[root * 2] = 1;
set_tag[root * 2 + 1] = 1;
add_tag[root * 2] = 0;
add_tag[root * 2 + 1] = 0;
set_lazy[root * 2] = set_lazy[root];
set_lazy[root * 2 + 1] = set_lazy[root];
add_lazy[root * 2] = line(0, 0);
add_lazy[root * 2 + 1] = line(0, 0);
}
else
{
d[left] = set_lazy[root].math(left);
}
set_tag[root] = 0;
set_lazy[root] = line(0, 0);
}
if (add_tag[root] == 1)
{
if (left != right)
{
add_tag[root * 2] = 1;
add_tag[root * 2 + 1] = 1;
add_lazy[root * 2].add_line(add_lazy[root]);
add_lazy[root * 2 + 1].add_line(add_lazy[root]);
}
else
{
d[left] += add_lazy[root].math(left);
}
add_tag[root] = 0;
add_lazy[root] = line(0, 0);
}
}
void set_line(int root, int left, int right, int qleft, int qright, line cur)
{
push_lazy(root, left, right);
if (left > qright || right < qleft)
return;
if (left >= qleft && right <= qright)
{
set_tag[root] = 1;
set_lazy[root] = cur;
push_lazy(root, left, right);
return;
}
int mid = (left + right) / 2;
set_line(root * 2, left, mid, qleft, qright, cur);
set_line(root * 2 + 1, mid + 1, right, qleft, qright, cur);
}
void add_line(int root, int left, int right, int qleft, int qright, line cur)
{
push_lazy(root, left, right);
if (left > qright || right < qleft)
return;
if (left >= qleft && right <= qright)
{
add_tag[root] = 1;
add_lazy[root] = cur;
push_lazy(root, left, right);
return;
}
int mid = (left + right) / 2;
add_line(root * 2, left, mid, qleft, qright, cur);
add_line(root * 2 + 1, mid + 1, right, qleft, qright, cur);
}
ll query(int root, int left, int right, int pos)
{
push_lazy(root, left, right);
if (left == right)
return d[left];
int mid = (left + right) / 2;
if (pos <= mid)
return query(root * 2, left, mid, pos);
return query(root * 2 + 1, mid + 1, right, pos);
}
/**void add_line_concious(int root, int left, int right, line cur)
{
push_lazy(root, left, right);
int mid = (left + right) / 2;
if (li_chao[root].math(mid) < cur.math(mid))
swap(li_chao[root], cur);
if (left == right)
return;
if ()
}*/
struct node
{
int pref, suff, lon, len;
ll fs, ls;
node(int _pref = 0, int _suff = 0, int _lon = 0, ll _fs = -inf, ll _ls = inf, int _len = 0)
{
len = _len;
pref = _pref;
suff = _suff;
lon = _lon;
fs = _fs;
ls = _ls;
}
};
node merge_nodes(node lf, node rf)
{
if (lf.ls == inf)
return rf;
if (rf.fs == -inf)
return lf;
node mf;
mf.fs = lf.fs;
mf.ls = rf.ls;
mf.pref = lf.pref;
if (lf.pref == lf.len && lf.ls == rf.fs)
mf.pref += rf.pref;
mf.suff = rf.suff;
if (rf.suff == rf.len && rf.fs == lf.ls)
mf.suff += lf.suff;
mf.lon = max(lf.lon, rf.lon);
if (lf.ls == rf.fs)
mf.lon = max(mf.lon, lf.suff + rf.pref);
mf.len = lf.len + rf.len;
return mf;
}
node tree[4 * maxn];
pair < ll, ll > lazy[4 * maxn];
pair < int, int > tag[4 * maxn];
void make_lazy(int root, int left, int right)
{
if (tag[root].first)
{
int len = right - left + 1;
tree[root] = node(len, len, len, lazy[root].first, lazy[root].first, len);
if (left != right)
{
tag[root * 2].first = 1;
tag[root * 2 + 1].first = 1;
tag[root * 2].second = 0;
tag[root * 2 + 1].second = 0;
lazy[root * 2].second = 0;
lazy[root * 2 + 1].second = 0;
lazy[root * 2].first = lazy[root].first;
lazy[root * 2 + 1].first = lazy[root].first;
}
lazy[root].first = 0;
tag[root].first = 0;
}
if (tag[root].second)
{
tree[root].fs += lazy[root].second;
tree[root].ls += lazy[root].second;
if (left != right)
{
tag[root * 2].second = 1;
tag[root * 2 + 1].second = 1;
lazy[root * 2].second = lazy[root].second;
lazy[root * 2 + 1].second = lazy[root].second;
}
tag[root].second = 0;
lazy[root].second = 0;
}
}
void range_update_set(int root, int left, int right, int qleft, int qright, ll val)
{
make_lazy(root, left, right);
if (left > qright || right < qleft)
return;
if (left >= qleft && right <= qright)
{
lazy[root].first = val;
tag[root].first = 1;
make_lazy(root, left, right);
return;
}
int mid = (left + right) / 2;
range_update_set(root * 2, left, mid, qleft, qright, val);
range_update_set(root * 2 + 1, mid + 1, right, qleft, qright, val);
tree[root] = merge_nodes(tree[root * 2], tree[root * 2 + 1]);
}
void range_update_add(int root, int left, int right, int qleft, int qright, ll val)
{
make_lazy(root, left, right);
if (left > qright || right < qleft)
return;
if (left >= qleft && right <= qright)
{
lazy[root].second =val;
tag[root].second = 1;
make_lazy(root, left, right);
return;
}
int mid = (left + right) / 2;
range_update_add(root * 2, left, mid, qleft, qright, val);
range_update_add(root * 2 + 1, mid + 1, right, qleft, qright, val);
tree[root] = merge_nodes(tree[root * 2], tree[root * 2 + 1]);
}
node query_range(int root, int left, int right, int qleft, int qright)
{
make_lazy(root, left, right);
if (left > qright || right < qleft)
return node();
if (left >= qleft && right <= qright)
{
return tree[root];
}
int mid = (left + right) / 2;
return merge_nodes(query_range(root * 2, left, mid, qleft, qright),
query_range(root * 2 + 1, mid + 1, right, qleft, qright));
}
void build_tree(int root, int left, int right)
{
if (left == right)
{
tree[root] = node(1, 1, 1, b[left], b[left], 1);
return;
}
int mid = (left + right) / 2;
build_tree(root * 2, left, mid);
build_tree(root * 2 + 1, mid + 1, right);
tree[root] = merge_nodes(tree[root * 2], tree[root * 2 + 1]);
}
void simulate()
{
build_tree(1, 1, n);
for (int i = 1; i <= q; i ++)
{
int type, l, r;
ll s, c;
cin >> type >> l >> r;
if (type == 3)
{
node cur = query_range(1, 1, n, l + 1, r);
cout << cur.lon + 1 << endl;
///cout << query(l, r) << endl;
}
else if (type == 1)
{
cin >> s >> c;
add_line(1, 1, n, l, r, line(c, - l * c + s));
/*for (int j = l; j <= r; j ++)
{
d[j] += s + (ll)(j - l) * c;
}*/
range_update_add(1, 1, n, l + 1, r, c);
range_update_add(1, 1, n, l, l, s);
b[l] += s;
for (int j = l + 1; j <= r; j ++)
b[j] += c;
if (r + 1 <= n)
range_update_set(1, 1, n, r + 1, r + 1, query(1, 1, n, r + 1) - query(1, 1, n, r));
b[r + 1] = query(1, 1, n, r + 1) - query(1, 1, n, r); ///d[r + 1] - d[r];
}
else
{
cin >> s >> c;
set_line(1, 1, n, l, r, line(c, - l * c + s));
/**for (int j = l; j <= r; j ++)
{
d[j] = s + (ll)(j - l) * c;
}*/
range_update_set(1, 1, n, l + 1, r, c);
for (int j = l + 1; j <= r; j ++)
b[j] = c;
range_update_set(1, 1, n, l, l, query(1, 1, n, l) - query(1, 1, n, l - 1));
b[l] = query(1, 1, n, l) - query(1, 1, n, l - 1); ///d[l] - d[l - 1];
if (r + 1 <= n)
range_update_set(1, 1, n, r + 1, r + 1, query(1, 1, n, r + 1) - query(1, 1, n, r));
b[r + 1] = query(1, 1, n, r + 1) - query(1, 1, n, r); ///d[r + 1] - d[r];
}
for (int j = 2; j <= n; j ++)
{
if (b[j] != query_range(1, 1, n, j, j).fs)
{
while(true);
}
}
/**for (int j = 1; j <= n; j ++)
{
b[j] = d[j] - d[j - 1];
}*/
/**for (int j = 1; j <= n; j ++)
cout << d[j] << " ";
cout << endl;*/
}
}
void solve()
{
input();
simulate();
}
int main()
{
speed();
solve();
return 0;
}
Compilation message
Progression.cpp: In function 'void push_lazy(int, int, int)':
Progression.cpp:93:9: warning: unused variable 'mid' [-Wunused-variable]
93 | int mid = (left + right) / 2;
| ^~~
Progression.cpp: In function 'void simulate()':
Progression.cpp:378:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
378 | for (int j = l + 1; j <= r; j ++)
| ^~~
Progression.cpp:380:17: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
380 | if (r + 1 <= n)
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3012 ms |
113848 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
225 ms |
82584 KB |
Output is correct |
| 2 |
Correct |
20 ms |
82524 KB |
Output is correct |
| 3 |
Correct |
19 ms |
82524 KB |
Output is correct |
| 4 |
Correct |
21 ms |
82520 KB |
Output is correct |
| 5 |
Correct |
17 ms |
82548 KB |
Output is correct |
| 6 |
Correct |
16 ms |
82540 KB |
Output is correct |
| 7 |
Correct |
16 ms |
82552 KB |
Output is correct |
| 8 |
Correct |
222 ms |
82768 KB |
Output is correct |
| 9 |
Correct |
219 ms |
82568 KB |
Output is correct |
| 10 |
Correct |
220 ms |
82520 KB |
Output is correct |
| 11 |
Correct |
224 ms |
82568 KB |
Output is correct |
| 12 |
Correct |
221 ms |
82520 KB |
Output is correct |
| 13 |
Correct |
217 ms |
82524 KB |
Output is correct |
| 14 |
Correct |
222 ms |
82524 KB |
Output is correct |
| 15 |
Correct |
219 ms |
82524 KB |
Output is correct |
| 16 |
Correct |
228 ms |
82580 KB |
Output is correct |
| 17 |
Correct |
220 ms |
82520 KB |
Output is correct |
| 18 |
Correct |
238 ms |
82580 KB |
Output is correct |
| 19 |
Correct |
21 ms |
82524 KB |
Output is correct |
| 20 |
Correct |
19 ms |
82444 KB |
Output is correct |
| 21 |
Correct |
19 ms |
82524 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3046 ms |
85080 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3035 ms |
97900 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3046 ms |
85080 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3012 ms |
113848 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
