#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;
#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())
struct node {
ll lazyAsgn, lazyAdd, sum;
ll best, preLen, preVal, sufLen, sufVal, same, len;
node() : lazyAsgn(0), lazyAdd(0), sum(0), best(0), preLen(0), preVal(0), sufLen(0), sufVal(0), same(0), len(0) {}
void refine (node ln, node rn) {
best = max({ln.best, rn.best, (ln.sufLen + rn.preLen) * (ln.sufVal == rn.preVal)});
preLen = max(ln.preLen, (ln.len + rn.preLen) * (ln.same == rn.preVal));
preVal = ln.preVal;
sufLen = max(rn.sufLen, (ln.sufLen + rn.len) * (ln.sufVal == rn.same));
sufVal = rn.sufVal;
same = (ln.same == rn.same ? ln.same : LLONG_MAX);
sum = ln.sum + rn.sum, len = ln.len + rn.len;
}
void applyAsgn (ll val, int l, int r) {
lazyAsgn = val, lazyAdd = 0, sum = val * ll(r - l + 1);
best = preLen = sufLen = r - l + 1;
preVal = sufVal = same = val, len = r - l + 1;
}
void applyAdd (ll incr, int l, int r) {
lazyAdd += incr, sum += incr * ll(r - l + 1);
preVal += incr, sufVal += incr, len = r - l + 1;
if (same != LLONG_MAX) same += incr;
}
void pushDown (node &ln, node &rn, int l, int r, int mid) {
if (lazyAsgn != LLONG_MAX) {
ln.applyAsgn(lazyAsgn, l, mid);
rn.applyAsgn(lazyAsgn, mid + 1, r);
}
if (lazyAdd != 0) {
ln.applyAdd(lazyAdd, l, mid);
rn.applyAdd(lazyAdd, mid + 1, r);
}
lazyAsgn = LLONG_MAX, lazyAdd = 0;
}
};
struct IT {
vector<node> tr;
IT (int sz) : tr(4 * sz) {}
void rangeAssign (int a, int b, ll val, int k, int l, int r) {
if (b < l || r < a) return;
if (a <= l && r <= b) {
tr[k].applyAsgn(val, l, r);
return;
}
int mid = (l + r) >> 1;
tr[k].pushDown(tr[2 * k], tr[2 * k + 1], l, r, mid);
rangeAssign(a, b, val, 2 * k, l, mid);
rangeAssign(a, b, val, 2 * k + 1, mid + 1, r);
tr[k].refine(tr[2 * k], tr[2 * k + 1]);
}
void rangeAdd (int a, int b, ll incr, int k, int l, int r) {
if (b < l || r < a) return;
if (a <= l && r <= b) {
tr[k].applyAdd(incr, l, r);
return;
}
int mid = (l + r) >> 1;
tr[k].pushDown(tr[2 * k], tr[2 * k + 1], l, r, mid);
rangeAdd(a, b, incr, 2 * k, l, mid);
rangeAdd(a, b, incr, 2 * k + 1, mid + 1, r);
tr[k].refine(tr[2 * k], tr[2 * k + 1]);
}
ll querySum (int a, int b, int k, int l, int r) {
if (b < l || r < a) return 0;
if (a <= l && r <= b) return tr[k].sum;
int mid = (l + r) >> 1;
tr[k].pushDown(tr[2 * k], tr[2 * k + 1], l, r, mid);
return querySum(a, b, 2 * k, l, mid) + querySum(a, b, 2 * k + 1, mid + 1, r);
}
node query (int a, int b, int k, int l, int r) {
if (b < l || r < a) return node();
if (a <= l && r <= b) return tr[k];
int mid = (l + r) >> 1;
tr[k].pushDown(tr[2 * k], tr[2 * k + 1], l, r, mid);
node ans; ans.refine(query(a, b, 2 * k, l, mid), query(a, b, 2 * k + 1, mid + 1, r));
return ans;
}
ll longestSame (int a, int b, int k, int l, int r) {
return query(a, b, k, l, r).best;
}
void lineAssign (int a, int b, ll S, ll C, int k, int l, int r) {
if (b < r) {
ll incrR = querySum(1, b + 1, k, l, r) - (S + ll(b - a) * C);
rangeAssign(b + 1, b + 1, incrR, k, l, r);
}
ll incrL = S - (a == l ? 0 : querySum(1, a - 1, k, l, r));
rangeAssign(a, a, incrL, k, l, r);
if (a < b) rangeAssign(a + 1, b, C, k, l, r);
}
void lineAdd (int a, int b, ll S, ll C, int k, int l, int r) {
if (b < r)
rangeAdd(b + 1, b + 1, -(S + ll(b - a) * C), k, l, r);
rangeAdd(a, a, S, k, l, r);
if (a < b) rangeAdd(a + 1, b, C, k, l, r);
}
};
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, q; cin >> n >> q;
IT tree(n);
for (int i = 1; i <= n; i++) {
int D; cin >> D;
tree.lineAssign(i, i, D, 0, 1, 1, n);
}
while (q--) {
int type, L, R; cin >> type >> L >> R;
if (type == 1) {
int S, C; cin >> S >> C;
tree.lineAdd(L, R, S, C, 1, 1, n);
}
else if (type == 2) {
int S, C; cin >> S >> C;
tree.lineAssign(L, R, S, C, 1, 1, n);
}
else {
if (L == R) cout << 1 << "\n";
else cout << tree.longestSame(L + 1, R, 1, 1, n) + 1 << "\n";
}
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
476 ms |
99152 KB |
Output is correct |
2 |
Correct |
90 ms |
2592 KB |
Output is correct |
3 |
Correct |
85 ms |
2348 KB |
Output is correct |
4 |
Correct |
114 ms |
2388 KB |
Output is correct |
5 |
Correct |
98 ms |
2388 KB |
Output is correct |
6 |
Correct |
85 ms |
2392 KB |
Output is correct |
7 |
Correct |
96 ms |
2360 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
485 ms |
99268 KB |
Output is correct |
12 |
Correct |
466 ms |
99080 KB |
Output is correct |
13 |
Correct |
487 ms |
99412 KB |
Output is correct |
14 |
Correct |
476 ms |
99668 KB |
Output is correct |
15 |
Correct |
479 ms |
99152 KB |
Output is correct |
16 |
Correct |
490 ms |
99096 KB |
Output is correct |
17 |
Correct |
489 ms |
99372 KB |
Output is correct |
18 |
Correct |
463 ms |
99152 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1116 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
2 ms |
600 KB |
Output is correct |
9 |
Correct |
2 ms |
604 KB |
Output is correct |
10 |
Correct |
2 ms |
604 KB |
Output is correct |
11 |
Correct |
2 ms |
604 KB |
Output is correct |
12 |
Correct |
2 ms |
604 KB |
Output is correct |
13 |
Correct |
1 ms |
604 KB |
Output is correct |
14 |
Correct |
2 ms |
604 KB |
Output is correct |
15 |
Correct |
2 ms |
604 KB |
Output is correct |
16 |
Correct |
2 ms |
664 KB |
Output is correct |
17 |
Correct |
2 ms |
604 KB |
Output is correct |
18 |
Correct |
2 ms |
700 KB |
Output is correct |
19 |
Correct |
1 ms |
344 KB |
Output is correct |
20 |
Correct |
1 ms |
348 KB |
Output is correct |
21 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
481 ms |
98724 KB |
Output is correct |
2 |
Correct |
65 ms |
2132 KB |
Output is correct |
3 |
Correct |
64 ms |
2132 KB |
Output is correct |
4 |
Correct |
54 ms |
2132 KB |
Output is correct |
5 |
Correct |
65 ms |
2388 KB |
Output is correct |
6 |
Correct |
74 ms |
2304 KB |
Output is correct |
7 |
Correct |
65 ms |
2368 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
456 KB |
Output is correct |
11 |
Correct |
503 ms |
97816 KB |
Output is correct |
12 |
Correct |
490 ms |
98644 KB |
Output is correct |
13 |
Correct |
504 ms |
97872 KB |
Output is correct |
14 |
Correct |
501 ms |
97928 KB |
Output is correct |
15 |
Correct |
491 ms |
98640 KB |
Output is correct |
16 |
Correct |
500 ms |
98896 KB |
Output is correct |
17 |
Correct |
506 ms |
98900 KB |
Output is correct |
18 |
Correct |
521 ms |
99096 KB |
Output is correct |
19 |
Correct |
473 ms |
98572 KB |
Output is correct |
20 |
Correct |
475 ms |
98204 KB |
Output is correct |
21 |
Correct |
484 ms |
98384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
660 ms |
99664 KB |
Output is correct |
2 |
Correct |
91 ms |
2384 KB |
Output is correct |
3 |
Correct |
95 ms |
2384 KB |
Output is correct |
4 |
Correct |
93 ms |
2368 KB |
Output is correct |
5 |
Correct |
96 ms |
2384 KB |
Output is correct |
6 |
Correct |
95 ms |
2268 KB |
Output is correct |
7 |
Correct |
110 ms |
2384 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
640 ms |
97968 KB |
Output is correct |
12 |
Correct |
644 ms |
99568 KB |
Output is correct |
13 |
Correct |
656 ms |
97904 KB |
Output is correct |
14 |
Correct |
653 ms |
97904 KB |
Output is correct |
15 |
Correct |
647 ms |
99664 KB |
Output is correct |
16 |
Correct |
665 ms |
99668 KB |
Output is correct |
17 |
Correct |
659 ms |
99664 KB |
Output is correct |
18 |
Correct |
672 ms |
99736 KB |
Output is correct |
19 |
Correct |
660 ms |
99564 KB |
Output is correct |
20 |
Correct |
647 ms |
99604 KB |
Output is correct |
21 |
Correct |
676 ms |
99680 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
481 ms |
98724 KB |
Output is correct |
2 |
Correct |
65 ms |
2132 KB |
Output is correct |
3 |
Correct |
64 ms |
2132 KB |
Output is correct |
4 |
Correct |
54 ms |
2132 KB |
Output is correct |
5 |
Correct |
65 ms |
2388 KB |
Output is correct |
6 |
Correct |
74 ms |
2304 KB |
Output is correct |
7 |
Correct |
65 ms |
2368 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
456 KB |
Output is correct |
11 |
Correct |
503 ms |
97816 KB |
Output is correct |
12 |
Correct |
490 ms |
98644 KB |
Output is correct |
13 |
Correct |
504 ms |
97872 KB |
Output is correct |
14 |
Correct |
501 ms |
97928 KB |
Output is correct |
15 |
Correct |
491 ms |
98640 KB |
Output is correct |
16 |
Correct |
500 ms |
98896 KB |
Output is correct |
17 |
Correct |
506 ms |
98900 KB |
Output is correct |
18 |
Correct |
521 ms |
99096 KB |
Output is correct |
19 |
Correct |
473 ms |
98572 KB |
Output is correct |
20 |
Correct |
475 ms |
98204 KB |
Output is correct |
21 |
Correct |
484 ms |
98384 KB |
Output is correct |
22 |
Correct |
772 ms |
99188 KB |
Output is correct |
23 |
Correct |
99 ms |
2308 KB |
Output is correct |
24 |
Correct |
97 ms |
2388 KB |
Output is correct |
25 |
Correct |
96 ms |
2468 KB |
Output is correct |
26 |
Correct |
103 ms |
2384 KB |
Output is correct |
27 |
Correct |
102 ms |
2384 KB |
Output is correct |
28 |
Correct |
98 ms |
2388 KB |
Output is correct |
29 |
Correct |
0 ms |
344 KB |
Output is correct |
30 |
Correct |
1 ms |
348 KB |
Output is correct |
31 |
Correct |
0 ms |
348 KB |
Output is correct |
32 |
Correct |
741 ms |
97940 KB |
Output is correct |
33 |
Correct |
778 ms |
99152 KB |
Output is correct |
34 |
Correct |
760 ms |
98136 KB |
Output is correct |
35 |
Correct |
745 ms |
98076 KB |
Output is correct |
36 |
Correct |
697 ms |
98140 KB |
Output is correct |
37 |
Correct |
662 ms |
98276 KB |
Output is correct |
38 |
Correct |
697 ms |
98040 KB |
Output is correct |
39 |
Correct |
766 ms |
99156 KB |
Output is correct |
40 |
Correct |
782 ms |
99668 KB |
Output is correct |
41 |
Correct |
813 ms |
99960 KB |
Output is correct |
42 |
Correct |
804 ms |
99664 KB |
Output is correct |
43 |
Correct |
762 ms |
99296 KB |
Output is correct |
44 |
Correct |
765 ms |
99292 KB |
Output is correct |
45 |
Correct |
731 ms |
99340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
476 ms |
99152 KB |
Output is correct |
2 |
Correct |
90 ms |
2592 KB |
Output is correct |
3 |
Correct |
85 ms |
2348 KB |
Output is correct |
4 |
Correct |
114 ms |
2388 KB |
Output is correct |
5 |
Correct |
98 ms |
2388 KB |
Output is correct |
6 |
Correct |
85 ms |
2392 KB |
Output is correct |
7 |
Correct |
96 ms |
2360 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
485 ms |
99268 KB |
Output is correct |
12 |
Correct |
466 ms |
99080 KB |
Output is correct |
13 |
Correct |
487 ms |
99412 KB |
Output is correct |
14 |
Correct |
476 ms |
99668 KB |
Output is correct |
15 |
Correct |
479 ms |
99152 KB |
Output is correct |
16 |
Correct |
490 ms |
99096 KB |
Output is correct |
17 |
Correct |
489 ms |
99372 KB |
Output is correct |
18 |
Correct |
463 ms |
99152 KB |
Output is correct |
19 |
Correct |
3 ms |
1116 KB |
Output is correct |
20 |
Correct |
1 ms |
344 KB |
Output is correct |
21 |
Correct |
1 ms |
348 KB |
Output is correct |
22 |
Correct |
1 ms |
348 KB |
Output is correct |
23 |
Correct |
1 ms |
344 KB |
Output is correct |
24 |
Correct |
1 ms |
348 KB |
Output is correct |
25 |
Correct |
1 ms |
348 KB |
Output is correct |
26 |
Correct |
2 ms |
600 KB |
Output is correct |
27 |
Correct |
2 ms |
604 KB |
Output is correct |
28 |
Correct |
2 ms |
604 KB |
Output is correct |
29 |
Correct |
2 ms |
604 KB |
Output is correct |
30 |
Correct |
2 ms |
604 KB |
Output is correct |
31 |
Correct |
1 ms |
604 KB |
Output is correct |
32 |
Correct |
2 ms |
604 KB |
Output is correct |
33 |
Correct |
2 ms |
604 KB |
Output is correct |
34 |
Correct |
2 ms |
664 KB |
Output is correct |
35 |
Correct |
2 ms |
604 KB |
Output is correct |
36 |
Correct |
2 ms |
700 KB |
Output is correct |
37 |
Correct |
1 ms |
344 KB |
Output is correct |
38 |
Correct |
1 ms |
348 KB |
Output is correct |
39 |
Correct |
1 ms |
348 KB |
Output is correct |
40 |
Correct |
481 ms |
98724 KB |
Output is correct |
41 |
Correct |
65 ms |
2132 KB |
Output is correct |
42 |
Correct |
64 ms |
2132 KB |
Output is correct |
43 |
Correct |
54 ms |
2132 KB |
Output is correct |
44 |
Correct |
65 ms |
2388 KB |
Output is correct |
45 |
Correct |
74 ms |
2304 KB |
Output is correct |
46 |
Correct |
65 ms |
2368 KB |
Output is correct |
47 |
Correct |
0 ms |
348 KB |
Output is correct |
48 |
Correct |
0 ms |
348 KB |
Output is correct |
49 |
Correct |
1 ms |
456 KB |
Output is correct |
50 |
Correct |
503 ms |
97816 KB |
Output is correct |
51 |
Correct |
490 ms |
98644 KB |
Output is correct |
52 |
Correct |
504 ms |
97872 KB |
Output is correct |
53 |
Correct |
501 ms |
97928 KB |
Output is correct |
54 |
Correct |
491 ms |
98640 KB |
Output is correct |
55 |
Correct |
500 ms |
98896 KB |
Output is correct |
56 |
Correct |
506 ms |
98900 KB |
Output is correct |
57 |
Correct |
521 ms |
99096 KB |
Output is correct |
58 |
Correct |
473 ms |
98572 KB |
Output is correct |
59 |
Correct |
475 ms |
98204 KB |
Output is correct |
60 |
Correct |
484 ms |
98384 KB |
Output is correct |
61 |
Correct |
660 ms |
99664 KB |
Output is correct |
62 |
Correct |
91 ms |
2384 KB |
Output is correct |
63 |
Correct |
95 ms |
2384 KB |
Output is correct |
64 |
Correct |
93 ms |
2368 KB |
Output is correct |
65 |
Correct |
96 ms |
2384 KB |
Output is correct |
66 |
Correct |
95 ms |
2268 KB |
Output is correct |
67 |
Correct |
110 ms |
2384 KB |
Output is correct |
68 |
Correct |
1 ms |
344 KB |
Output is correct |
69 |
Correct |
1 ms |
348 KB |
Output is correct |
70 |
Correct |
0 ms |
348 KB |
Output is correct |
71 |
Correct |
640 ms |
97968 KB |
Output is correct |
72 |
Correct |
644 ms |
99568 KB |
Output is correct |
73 |
Correct |
656 ms |
97904 KB |
Output is correct |
74 |
Correct |
653 ms |
97904 KB |
Output is correct |
75 |
Correct |
647 ms |
99664 KB |
Output is correct |
76 |
Correct |
665 ms |
99668 KB |
Output is correct |
77 |
Correct |
659 ms |
99664 KB |
Output is correct |
78 |
Correct |
672 ms |
99736 KB |
Output is correct |
79 |
Correct |
660 ms |
99564 KB |
Output is correct |
80 |
Correct |
647 ms |
99604 KB |
Output is correct |
81 |
Correct |
676 ms |
99680 KB |
Output is correct |
82 |
Correct |
772 ms |
99188 KB |
Output is correct |
83 |
Correct |
99 ms |
2308 KB |
Output is correct |
84 |
Correct |
97 ms |
2388 KB |
Output is correct |
85 |
Correct |
96 ms |
2468 KB |
Output is correct |
86 |
Correct |
103 ms |
2384 KB |
Output is correct |
87 |
Correct |
102 ms |
2384 KB |
Output is correct |
88 |
Correct |
98 ms |
2388 KB |
Output is correct |
89 |
Correct |
0 ms |
344 KB |
Output is correct |
90 |
Correct |
1 ms |
348 KB |
Output is correct |
91 |
Correct |
0 ms |
348 KB |
Output is correct |
92 |
Correct |
741 ms |
97940 KB |
Output is correct |
93 |
Correct |
778 ms |
99152 KB |
Output is correct |
94 |
Correct |
760 ms |
98136 KB |
Output is correct |
95 |
Correct |
745 ms |
98076 KB |
Output is correct |
96 |
Correct |
697 ms |
98140 KB |
Output is correct |
97 |
Correct |
662 ms |
98276 KB |
Output is correct |
98 |
Correct |
697 ms |
98040 KB |
Output is correct |
99 |
Correct |
766 ms |
99156 KB |
Output is correct |
100 |
Correct |
782 ms |
99668 KB |
Output is correct |
101 |
Correct |
813 ms |
99960 KB |
Output is correct |
102 |
Correct |
804 ms |
99664 KB |
Output is correct |
103 |
Correct |
762 ms |
99296 KB |
Output is correct |
104 |
Correct |
765 ms |
99292 KB |
Output is correct |
105 |
Correct |
731 ms |
99340 KB |
Output is correct |
106 |
Correct |
875 ms |
104528 KB |
Output is correct |
107 |
Correct |
121 ms |
3832 KB |
Output is correct |
108 |
Correct |
118 ms |
3668 KB |
Output is correct |
109 |
Correct |
118 ms |
3684 KB |
Output is correct |
110 |
Correct |
0 ms |
344 KB |
Output is correct |
111 |
Correct |
1 ms |
344 KB |
Output is correct |
112 |
Correct |
0 ms |
348 KB |
Output is correct |
113 |
Correct |
772 ms |
103636 KB |
Output is correct |
114 |
Correct |
770 ms |
103764 KB |
Output is correct |
115 |
Correct |
748 ms |
103512 KB |
Output is correct |
116 |
Correct |
750 ms |
103576 KB |
Output is correct |
117 |
Correct |
961 ms |
104472 KB |
Output is correct |
118 |
Correct |
762 ms |
103544 KB |
Output is correct |
119 |
Correct |
746 ms |
103584 KB |
Output is correct |
120 |
Correct |
533 ms |
102480 KB |
Output is correct |
121 |
Correct |
528 ms |
102176 KB |
Output is correct |
122 |
Correct |
535 ms |
102176 KB |
Output is correct |
123 |
Correct |
502 ms |
101204 KB |
Output is correct |
124 |
Correct |
501 ms |
101200 KB |
Output is correct |
125 |
Correct |
495 ms |
101200 KB |
Output is correct |
126 |
Correct |
895 ms |
101200 KB |
Output is correct |
127 |
Correct |
901 ms |
101200 KB |
Output is correct |
128 |
Correct |
914 ms |
104532 KB |
Output is correct |
129 |
Correct |
928 ms |
101328 KB |
Output is correct |
130 |
Correct |
710 ms |
101468 KB |
Output is correct |
131 |
Correct |
701 ms |
101200 KB |
Output is correct |
132 |
Correct |
692 ms |
101200 KB |
Output is correct |
133 |
Correct |
863 ms |
104512 KB |
Output is correct |
134 |
Correct |
871 ms |
104608 KB |
Output is correct |
135 |
Correct |
904 ms |
104492 KB |
Output is correct |
136 |
Correct |
116 ms |
3760 KB |
Output is correct |
137 |
Correct |
116 ms |
3668 KB |
Output is correct |
138 |
Correct |
117 ms |
3664 KB |
Output is correct |