#include <bits/stdc++.h>
using namespace std;
#define SZ(v) ((int)(v).size())
using ll = long long;
template<class T>
struct Segtree_rangeAdd_pointQuery
{
int nb_elem;
int LIM;
vector<T> seg;
int deb;
Segtree_rangeAdd_pointQuery(int N)
{
nb_elem = 1;
while (nb_elem < N)
nb_elem *= 2;
LIM = 4 * nb_elem;
deb = nb_elem-1;
seg.resize(LIM);
}
Segtree_rangeAdd_pointQuery(vector<T> arr)
{
*this = Segtree_rangeAdd_pointQuery(SZ(arr));
for (int i(0); i < SZ(arr); ++i)
seg[deb + i] = arr[i];
}
void add(int lo, int up, T delta)
{
lo += deb;
up += deb;
while (lo < up)
{
if (up%2)
seg[up] += delta;
if (lo%2==0)
seg[lo] += delta;
lo /= 2;
up = (up-2)/2;
}
if (lo == up)
seg[lo] += delta;
}
T query(int id)
{
id += deb;
T ans(seg[id]);
while (id)
{
id = (id-1)/2;
ans += seg[id];
}
return ans;
}
};
int main(void)
{
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
ll nb_elem, nb_requetes, up, down;
cin >> nb_elem >> nb_requetes >> up >> down;
vector<ll> arr(nb_elem+1);
for (auto &v : arr)
cin >> v;
Segtree_rangeAdd_pointQuery<ll> seg = Segtree_rangeAdd_pointQuery<ll>(arr);
ll temp(0);
auto find_delta = [&](ll a, ll b)
{
if (a >= b)
return -down * (b - a);
else
return -up * (b-a);
};
for (int i(0); i < nb_elem; ++i)
temp += find_delta(arr[i], arr[i+1]);
while (nb_requetes--)
{
ll L, R, delta;
cin >> L >> R >> delta;
ll u1 = seg.query(L-1);
ll u2 = seg.query(L);
ll v1 = seg.query(R);
ll v2 = (R < nb_elem ? seg.query(R+1) : v1);
temp -= find_delta(u1, u2);
temp -= find_delta(v1, v2);
seg.add(L, R, delta);
u2 = seg.query(L);
v1 = seg.query(R);
temp += find_delta(u1, u2);
if (R < nb_elem)
temp += find_delta(v1, v2);
cout << temp << '\n';
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
512 KB |
Output is correct |
2 |
Correct |
6 ms |
512 KB |
Output is correct |
3 |
Correct |
6 ms |
512 KB |
Output is correct |
4 |
Correct |
6 ms |
512 KB |
Output is correct |
5 |
Correct |
6 ms |
512 KB |
Output is correct |
6 |
Correct |
6 ms |
512 KB |
Output is correct |
7 |
Correct |
7 ms |
512 KB |
Output is correct |
8 |
Correct |
6 ms |
512 KB |
Output is correct |
9 |
Correct |
6 ms |
512 KB |
Output is correct |
10 |
Correct |
6 ms |
512 KB |
Output is correct |
11 |
Correct |
6 ms |
544 KB |
Output is correct |
12 |
Correct |
7 ms |
512 KB |
Output is correct |
13 |
Correct |
7 ms |
512 KB |
Output is correct |
14 |
Correct |
6 ms |
512 KB |
Output is correct |
15 |
Correct |
6 ms |
512 KB |
Output is correct |
16 |
Correct |
6 ms |
512 KB |
Output is correct |
17 |
Correct |
6 ms |
512 KB |
Output is correct |
18 |
Correct |
6 ms |
512 KB |
Output is correct |
19 |
Correct |
5 ms |
384 KB |
Output is correct |
20 |
Correct |
5 ms |
384 KB |
Output is correct |
21 |
Correct |
4 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
239 ms |
17068 KB |
Output is correct |
2 |
Correct |
230 ms |
17756 KB |
Output is correct |
3 |
Correct |
235 ms |
18196 KB |
Output is correct |
4 |
Correct |
229 ms |
17572 KB |
Output is correct |
5 |
Correct |
230 ms |
18812 KB |
Output is correct |
6 |
Correct |
155 ms |
17760 KB |
Output is correct |
7 |
Correct |
154 ms |
17704 KB |
Output is correct |
8 |
Correct |
230 ms |
18620 KB |
Output is correct |
9 |
Correct |
218 ms |
19036 KB |
Output is correct |
10 |
Correct |
223 ms |
17628 KB |
Output is correct |
11 |
Correct |
149 ms |
17756 KB |
Output is correct |
12 |
Correct |
150 ms |
18320 KB |
Output is correct |
13 |
Correct |
152 ms |
18652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
512 KB |
Output is correct |
2 |
Correct |
6 ms |
512 KB |
Output is correct |
3 |
Correct |
6 ms |
512 KB |
Output is correct |
4 |
Correct |
6 ms |
512 KB |
Output is correct |
5 |
Correct |
6 ms |
512 KB |
Output is correct |
6 |
Correct |
6 ms |
512 KB |
Output is correct |
7 |
Correct |
7 ms |
512 KB |
Output is correct |
8 |
Correct |
6 ms |
512 KB |
Output is correct |
9 |
Correct |
6 ms |
512 KB |
Output is correct |
10 |
Correct |
6 ms |
512 KB |
Output is correct |
11 |
Correct |
6 ms |
544 KB |
Output is correct |
12 |
Correct |
7 ms |
512 KB |
Output is correct |
13 |
Correct |
7 ms |
512 KB |
Output is correct |
14 |
Correct |
6 ms |
512 KB |
Output is correct |
15 |
Correct |
6 ms |
512 KB |
Output is correct |
16 |
Correct |
6 ms |
512 KB |
Output is correct |
17 |
Correct |
6 ms |
512 KB |
Output is correct |
18 |
Correct |
6 ms |
512 KB |
Output is correct |
19 |
Correct |
5 ms |
384 KB |
Output is correct |
20 |
Correct |
5 ms |
384 KB |
Output is correct |
21 |
Correct |
4 ms |
384 KB |
Output is correct |
22 |
Correct |
239 ms |
17068 KB |
Output is correct |
23 |
Correct |
230 ms |
17756 KB |
Output is correct |
24 |
Correct |
235 ms |
18196 KB |
Output is correct |
25 |
Correct |
229 ms |
17572 KB |
Output is correct |
26 |
Correct |
230 ms |
18812 KB |
Output is correct |
27 |
Correct |
155 ms |
17760 KB |
Output is correct |
28 |
Correct |
154 ms |
17704 KB |
Output is correct |
29 |
Correct |
230 ms |
18620 KB |
Output is correct |
30 |
Correct |
218 ms |
19036 KB |
Output is correct |
31 |
Correct |
223 ms |
17628 KB |
Output is correct |
32 |
Correct |
149 ms |
17756 KB |
Output is correct |
33 |
Correct |
150 ms |
18320 KB |
Output is correct |
34 |
Correct |
152 ms |
18652 KB |
Output is correct |
35 |
Correct |
208 ms |
17244 KB |
Output is correct |
36 |
Correct |
219 ms |
18652 KB |
Output is correct |
37 |
Correct |
230 ms |
19292 KB |
Output is correct |
38 |
Correct |
206 ms |
19140 KB |
Output is correct |
39 |
Correct |
218 ms |
19164 KB |
Output is correct |
40 |
Correct |
221 ms |
19208 KB |
Output is correct |
41 |
Correct |
209 ms |
19140 KB |
Output is correct |
42 |
Correct |
240 ms |
19036 KB |
Output is correct |
43 |
Correct |
203 ms |
18396 KB |
Output is correct |
44 |
Correct |
206 ms |
18780 KB |
Output is correct |
45 |
Correct |
202 ms |
18780 KB |
Output is correct |
46 |
Correct |
207 ms |
19932 KB |
Output is correct |
47 |
Correct |
157 ms |
18400 KB |
Output is correct |
48 |
Correct |
148 ms |
18524 KB |
Output is correct |
49 |
Correct |
201 ms |
17500 KB |
Output is correct |
50 |
Correct |
148 ms |
18268 KB |
Output is correct |
51 |
Correct |
156 ms |
18524 KB |
Output is correct |
52 |
Correct |
164 ms |
18524 KB |
Output is correct |