#include <cstdio>
#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <set>
#include <map>
#include <algorithm>
#include <fstream>
#include <cmath>
#include <queue>
#include <stack>
#include <cassert>
#include <cstring>
#include <climits>
#include <functional>
#include<cstdlib>
//#include "arc.h"
//#include "dreaming.h"
using namespace std;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef long long LL;
const int MAXN = 4e5 + 11;
using ll = long long;
const ll mod1 = 1e9 + 7;
const ll mod2 = 1000000021;
const ll P = 31;
void setIO(string name = "") {
cin.tie(0)->sync_with_stdio(0); // see /general/fast-io
if ((name.size())) {
//freopen((name + ".in").c_str(), "r", stdin); // see /general/input-output
//freopen((name + ".out").c_str(), "w", stdout);
}
}
ll n, q, S,T;
ll t[4 * MAXN];
ll lazy[4 * MAXN];
ll ans;
ll x[MAXN];
void push(int v,int tl,int tm,int tr)
{
if (lazy[v])
{
t[2 * v + 1] += (tr - tm) * lazy[v];
t[2 * v] += (tm - tl + 1) * (lazy[v]);
lazy[2 * v + 1] += lazy[v];
lazy[2 * v] += lazy[v];
lazy[v] = 0;
}
}
void upd(int v, int tl, int tr, int l, int r, ll val)
{
if (l > r)
return;
if (tl == l && tr == r)
{
t[v] += val * (tr - tl + 1);
lazy[v] += val;
return;
}
int tm = (tl + tr) / 2;
push(v, tl, tm, tr);
upd(2 * v, tl, tm, l, min(r, tm), val);
upd(2 * v + 1, tm + 1, tr, max(l, tm + 1), r, val);
t[v] = t[2 * v] + t[2 * v + 1];
}
ll query(int v, int tl, int tr, int l, int r)
{
if (l > r)
return 0;
if (tl == l && tr == r)
return t[v];
int tm = (tl + tr) / 2;
push(v, tl, tm, tr);
return query(2 * v, tl, tm, l, min(r, tm)) +
query(2 * v + 1, tm + 1, tr, max(l, tm + 1), r);
}
ll calc(int i1, int i2)
{
ll I1 = query(1, 0, MAXN, i1, i1);
ll I2 = query(1, 0, MAXN, i2, i2);
if (I1 < I2)
return -(I2 - I1) * S;
else
return (I1 - I2) * T;
}
int main()
{
cin.tie(0);
cout.tie(0);
ios_base::sync_with_stdio(false);
//setIO("radio");
cin >> n >> q >> S >> T;
for (int i = 0; i <= n; i++)
{
cin >> x[i];
upd(1, 0, MAXN, i, i, x[i]);
}
for (int i = 1; i <= n; i++)
{
if (x[i] > x[i - 1])
{
ans -= S * (x[i] - x[i - 1]);
}
else
ans += T * (x[i - 1] - x[i]);
}
for (int i = 0; i < q; i++)
{
ll a, b, d;
cin >> a >> b >> d;
ll L = calc(a - 1, a);
ll R = calc(b, b + 1);
upd(1, 0, MAXN, a, b, d);
if (a >= 1)
{
ans -= L;
ans += calc(a - 1, a);
}
if (b < n)
{
ans -= R;
ans += calc(b, b + 1);
}
cout << ans << '\n';
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
8540 KB |
Output is correct |
2 |
Correct |
5 ms |
8776 KB |
Output is correct |
3 |
Correct |
5 ms |
8792 KB |
Output is correct |
4 |
Correct |
6 ms |
8672 KB |
Output is correct |
5 |
Correct |
5 ms |
9048 KB |
Output is correct |
6 |
Correct |
6 ms |
8796 KB |
Output is correct |
7 |
Correct |
5 ms |
8812 KB |
Output is correct |
8 |
Correct |
5 ms |
8796 KB |
Output is correct |
9 |
Correct |
6 ms |
8796 KB |
Output is correct |
10 |
Correct |
5 ms |
8796 KB |
Output is correct |
11 |
Correct |
5 ms |
8796 KB |
Output is correct |
12 |
Correct |
5 ms |
8796 KB |
Output is correct |
13 |
Correct |
4 ms |
8796 KB |
Output is correct |
14 |
Correct |
4 ms |
8668 KB |
Output is correct |
15 |
Correct |
5 ms |
8796 KB |
Output is correct |
16 |
Correct |
4 ms |
8796 KB |
Output is correct |
17 |
Correct |
4 ms |
8796 KB |
Output is correct |
18 |
Correct |
4 ms |
8796 KB |
Output is correct |
19 |
Correct |
1 ms |
8660 KB |
Output is correct |
20 |
Correct |
1 ms |
8540 KB |
Output is correct |
21 |
Correct |
1 ms |
8540 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
463 ms |
18576 KB |
Output is correct |
2 |
Correct |
448 ms |
18956 KB |
Output is correct |
3 |
Correct |
471 ms |
19628 KB |
Output is correct |
4 |
Correct |
450 ms |
24404 KB |
Output is correct |
5 |
Correct |
456 ms |
25684 KB |
Output is correct |
6 |
Correct |
316 ms |
23648 KB |
Output is correct |
7 |
Correct |
279 ms |
23632 KB |
Output is correct |
8 |
Correct |
413 ms |
25536 KB |
Output is correct |
9 |
Correct |
462 ms |
25800 KB |
Output is correct |
10 |
Correct |
409 ms |
24476 KB |
Output is correct |
11 |
Correct |
308 ms |
23492 KB |
Output is correct |
12 |
Correct |
288 ms |
24296 KB |
Output is correct |
13 |
Correct |
289 ms |
24340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
8540 KB |
Output is correct |
2 |
Correct |
5 ms |
8776 KB |
Output is correct |
3 |
Correct |
5 ms |
8792 KB |
Output is correct |
4 |
Correct |
6 ms |
8672 KB |
Output is correct |
5 |
Correct |
5 ms |
9048 KB |
Output is correct |
6 |
Correct |
6 ms |
8796 KB |
Output is correct |
7 |
Correct |
5 ms |
8812 KB |
Output is correct |
8 |
Correct |
5 ms |
8796 KB |
Output is correct |
9 |
Correct |
6 ms |
8796 KB |
Output is correct |
10 |
Correct |
5 ms |
8796 KB |
Output is correct |
11 |
Correct |
5 ms |
8796 KB |
Output is correct |
12 |
Correct |
5 ms |
8796 KB |
Output is correct |
13 |
Correct |
4 ms |
8796 KB |
Output is correct |
14 |
Correct |
4 ms |
8668 KB |
Output is correct |
15 |
Correct |
5 ms |
8796 KB |
Output is correct |
16 |
Correct |
4 ms |
8796 KB |
Output is correct |
17 |
Correct |
4 ms |
8796 KB |
Output is correct |
18 |
Correct |
4 ms |
8796 KB |
Output is correct |
19 |
Correct |
1 ms |
8660 KB |
Output is correct |
20 |
Correct |
1 ms |
8540 KB |
Output is correct |
21 |
Correct |
1 ms |
8540 KB |
Output is correct |
22 |
Correct |
463 ms |
18576 KB |
Output is correct |
23 |
Correct |
448 ms |
18956 KB |
Output is correct |
24 |
Correct |
471 ms |
19628 KB |
Output is correct |
25 |
Correct |
450 ms |
24404 KB |
Output is correct |
26 |
Correct |
456 ms |
25684 KB |
Output is correct |
27 |
Correct |
316 ms |
23648 KB |
Output is correct |
28 |
Correct |
279 ms |
23632 KB |
Output is correct |
29 |
Correct |
413 ms |
25536 KB |
Output is correct |
30 |
Correct |
462 ms |
25800 KB |
Output is correct |
31 |
Correct |
409 ms |
24476 KB |
Output is correct |
32 |
Correct |
308 ms |
23492 KB |
Output is correct |
33 |
Correct |
288 ms |
24296 KB |
Output is correct |
34 |
Correct |
289 ms |
24340 KB |
Output is correct |
35 |
Correct |
465 ms |
23892 KB |
Output is correct |
36 |
Correct |
480 ms |
25392 KB |
Output is correct |
37 |
Correct |
467 ms |
26088 KB |
Output is correct |
38 |
Correct |
467 ms |
25868 KB |
Output is correct |
39 |
Correct |
471 ms |
25968 KB |
Output is correct |
40 |
Correct |
454 ms |
25876 KB |
Output is correct |
41 |
Correct |
485 ms |
25736 KB |
Output is correct |
42 |
Correct |
466 ms |
26016 KB |
Output is correct |
43 |
Correct |
453 ms |
25168 KB |
Output is correct |
44 |
Correct |
476 ms |
25620 KB |
Output is correct |
45 |
Correct |
487 ms |
25740 KB |
Output is correct |
46 |
Correct |
455 ms |
26628 KB |
Output is correct |
47 |
Correct |
303 ms |
24220 KB |
Output is correct |
48 |
Correct |
275 ms |
24148 KB |
Output is correct |
49 |
Correct |
441 ms |
24472 KB |
Output is correct |
50 |
Correct |
297 ms |
24312 KB |
Output is correct |
51 |
Correct |
287 ms |
24316 KB |
Output is correct |
52 |
Correct |
323 ms |
24648 KB |
Output is correct |