#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
typedef long long ll;
struct Node
{
ll sMaior=0, sMenor=0;
} tree[4*maxn];
int n;
int a[maxn];
ll bit[maxn];
void upd_bit(int x, int v)
{
for (; x < maxn; x += (x&-x))
bit[x] += 1ll*v;
}
ll soma(int x)
{
ll ans = 0;
for (; x > 0; x -= (x&-x))
ans += bit[x];
return ans;
}
void build(int node, int l, int r)
{
if (l == r)
{
if (l < n && a[l] >= a[l+1]) tree[node].sMaior = (a[l]-a[l+1]);
else if (l < n) tree[node].sMenor = (a[l+1]-a[l]);
return;
}
int mid = (l+r)>>1;
build(2*node, l, mid); build(2*node+1, mid+1, r);
tree[node].sMaior = tree[2*node].sMaior + tree[2*node+1].sMaior;
tree[node].sMenor = tree[2*node].sMenor + tree[2*node+1].sMenor;
}
void upd(int node, int l, int r, int pos, int op)
{
if (l == r)
{
ll val1 = 1ll*a[l] + soma(l);
ll val2 = 1ll*a[l+1] + soma(l+1);
if (val1 >= val2)
{
if (!op) tree[node].sMaior -= (val1-val2);
else tree[node].sMaior += (val1-val2);
}
else
{
if (!op) tree[node].sMenor -= (val2-val1);
else tree[node].sMenor += (val2-val1);
}
return;
}
int mid = (l+r)>>1;
if (pos <= mid) upd(2*node, l, mid, pos, op);
else upd(2*node+1, mid+1, r, pos, op);
tree[node].sMaior = tree[2*node].sMaior + tree[2*node+1].sMaior;
tree[node].sMenor = tree[2*node].sMenor + tree[2*node+1].sMenor;
}
int main(void)
{
int q, s, t;
scanf("%d %d %d %d", &n, &q, &s, &t);
for (int i = 0; i <= n; i++)
scanf("%d", &a[i]);
build(1, 0, n);
for (int i = 1; i <= q; i++)
{
int l, r, d;
scanf("%d %d %d", &l, &r, &d);
upd(1, 0, n, l-1, 0);
if (r != n) upd(1, 0, n, r, 0);
upd_bit(l, d); upd_bit(r+1, -d);
upd(1, 0, n, l-1, 1);
if (r != n) upd(1, 0, n, r, 1);
printf("%lld\n", 1ll*t*tree[1].sMaior - 1ll*s*tree[1].sMenor);
}
}
Compilation message
foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:84:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d", &n, &q, &s, &t);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foehn_phenomena.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a[i]);
~~~~~^~~~~~~~~~~~~
foehn_phenomena.cpp:94:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &l, &r, &d);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
504 KB |
Output is correct |
2 |
Correct |
5 ms |
504 KB |
Output is correct |
3 |
Correct |
5 ms |
504 KB |
Output is correct |
4 |
Correct |
5 ms |
504 KB |
Output is correct |
5 |
Correct |
5 ms |
504 KB |
Output is correct |
6 |
Correct |
5 ms |
504 KB |
Output is correct |
7 |
Correct |
5 ms |
504 KB |
Output is correct |
8 |
Correct |
5 ms |
504 KB |
Output is correct |
9 |
Correct |
5 ms |
552 KB |
Output is correct |
10 |
Correct |
5 ms |
504 KB |
Output is correct |
11 |
Correct |
5 ms |
504 KB |
Output is correct |
12 |
Correct |
5 ms |
504 KB |
Output is correct |
13 |
Correct |
4 ms |
504 KB |
Output is correct |
14 |
Correct |
4 ms |
504 KB |
Output is correct |
15 |
Correct |
5 ms |
504 KB |
Output is correct |
16 |
Correct |
4 ms |
504 KB |
Output is correct |
17 |
Correct |
4 ms |
504 KB |
Output is correct |
18 |
Correct |
4 ms |
504 KB |
Output is correct |
19 |
Correct |
2 ms |
376 KB |
Output is correct |
20 |
Correct |
18 ms |
376 KB |
Output is correct |
21 |
Correct |
3 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
399 ms |
17736 KB |
Output is correct |
2 |
Correct |
416 ms |
18372 KB |
Output is correct |
3 |
Correct |
410 ms |
19008 KB |
Output is correct |
4 |
Correct |
389 ms |
18424 KB |
Output is correct |
5 |
Correct |
399 ms |
19508 KB |
Output is correct |
6 |
Correct |
205 ms |
17144 KB |
Output is correct |
7 |
Correct |
210 ms |
16888 KB |
Output is correct |
8 |
Correct |
354 ms |
19328 KB |
Output is correct |
9 |
Correct |
356 ms |
19616 KB |
Output is correct |
10 |
Correct |
347 ms |
18428 KB |
Output is correct |
11 |
Correct |
237 ms |
16888 KB |
Output is correct |
12 |
Correct |
196 ms |
17528 KB |
Output is correct |
13 |
Correct |
205 ms |
17816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
504 KB |
Output is correct |
2 |
Correct |
5 ms |
504 KB |
Output is correct |
3 |
Correct |
5 ms |
504 KB |
Output is correct |
4 |
Correct |
5 ms |
504 KB |
Output is correct |
5 |
Correct |
5 ms |
504 KB |
Output is correct |
6 |
Correct |
5 ms |
504 KB |
Output is correct |
7 |
Correct |
5 ms |
504 KB |
Output is correct |
8 |
Correct |
5 ms |
504 KB |
Output is correct |
9 |
Correct |
5 ms |
552 KB |
Output is correct |
10 |
Correct |
5 ms |
504 KB |
Output is correct |
11 |
Correct |
5 ms |
504 KB |
Output is correct |
12 |
Correct |
5 ms |
504 KB |
Output is correct |
13 |
Correct |
4 ms |
504 KB |
Output is correct |
14 |
Correct |
4 ms |
504 KB |
Output is correct |
15 |
Correct |
5 ms |
504 KB |
Output is correct |
16 |
Correct |
4 ms |
504 KB |
Output is correct |
17 |
Correct |
4 ms |
504 KB |
Output is correct |
18 |
Correct |
4 ms |
504 KB |
Output is correct |
19 |
Correct |
2 ms |
376 KB |
Output is correct |
20 |
Correct |
18 ms |
376 KB |
Output is correct |
21 |
Correct |
3 ms |
376 KB |
Output is correct |
22 |
Correct |
399 ms |
17736 KB |
Output is correct |
23 |
Correct |
416 ms |
18372 KB |
Output is correct |
24 |
Correct |
410 ms |
19008 KB |
Output is correct |
25 |
Correct |
389 ms |
18424 KB |
Output is correct |
26 |
Correct |
399 ms |
19508 KB |
Output is correct |
27 |
Correct |
205 ms |
17144 KB |
Output is correct |
28 |
Correct |
210 ms |
16888 KB |
Output is correct |
29 |
Correct |
354 ms |
19328 KB |
Output is correct |
30 |
Correct |
356 ms |
19616 KB |
Output is correct |
31 |
Correct |
347 ms |
18428 KB |
Output is correct |
32 |
Correct |
237 ms |
16888 KB |
Output is correct |
33 |
Correct |
196 ms |
17528 KB |
Output is correct |
34 |
Correct |
205 ms |
17816 KB |
Output is correct |
35 |
Correct |
401 ms |
17856 KB |
Output is correct |
36 |
Correct |
411 ms |
19272 KB |
Output is correct |
37 |
Correct |
411 ms |
20044 KB |
Output is correct |
38 |
Correct |
410 ms |
19832 KB |
Output is correct |
39 |
Correct |
412 ms |
19844 KB |
Output is correct |
40 |
Correct |
427 ms |
19968 KB |
Output is correct |
41 |
Correct |
413 ms |
19684 KB |
Output is correct |
42 |
Correct |
417 ms |
19964 KB |
Output is correct |
43 |
Correct |
406 ms |
19028 KB |
Output is correct |
44 |
Correct |
414 ms |
19440 KB |
Output is correct |
45 |
Correct |
391 ms |
19520 KB |
Output is correct |
46 |
Correct |
401 ms |
20540 KB |
Output is correct |
47 |
Correct |
208 ms |
17548 KB |
Output is correct |
48 |
Correct |
259 ms |
17528 KB |
Output is correct |
49 |
Correct |
383 ms |
18168 KB |
Output is correct |
50 |
Correct |
240 ms |
17400 KB |
Output is correct |
51 |
Correct |
196 ms |
17784 KB |
Output is correct |
52 |
Correct |
262 ms |
17660 KB |
Output is correct |