#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define fi first
#define si second
typedef pair<int,int> pi;
#ifdef LOCAL
#define debug(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) 69
#endif
template <typename Arg>
void __f(string name, Arg arg) {
cerr << name << " = " << arg << endl;
}
template <typename Head, typename... Tail>
void __f(string names, Head head, Tail... tail) {
string cur = "";
for (auto ch: names){if(ch==','){break;}else{cur+=ch;}}
string nxt = names.substr(cur.size()+2);
cerr << cur << " = " << head << ", ";
__f(nxt, tail...);
}
const int mxn = 200005;
int N, Q, S, T, ret;
int A[mxn], fw[mxn], fw2[mxn];
void update(int x, int y, int v) {
for (int tx=x; tx <= N; tx += tx&(-tx)) fw[tx] += v, fw2[tx] -= v*(x-1);
for (int ty=y+1; ty <= N; ty += ty&(-ty)) fw[ty] -= v, fw2[ty] += v*y;
}
int sum(int x) {
int res = 0;
for (int tx=x; tx; tx -= tx&(-tx)) res += fw[tx]*x + fw2[tx];
return res;
}
int query(int x, int y) {
if (x == 0) return A[0];
return sum(y)-sum(x-1);
}
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N >> Q >> S >> T;
for (int i = 0; i <= N; ++i) {
cin >> A[i];
if (i) update(i, i, A[i]);
}
for (int i = 0; i < N; ++i) {
int dif = abs(A[i] - A[i + 1]);
if (A[i] < A[i + 1]) ret -= dif * S;
else ret += dif * T;
}
while (Q--) {
int l, r, k;
cin >> l >> r >> k;
int lv = query(l - 1, l - 1), rv = query(r + 1, r + 1);
int dif_l = query(l, l) - lv, dif_r = rv - query(r, r);
if (dif_l > 0) ret += abs(dif_l) * S;
else ret -= abs(dif_l) * T;
if (r != N) {
if (dif_r > 0) ret += abs(dif_r) * S;
else ret -= abs(dif_r) * T;
}
update(l, r, k);
dif_l = query(l, l) - lv, dif_r = rv - query(r, r);
if (dif_l > 0) ret -= abs(dif_l) * S;
else ret += abs(dif_l) * T;
if (r != N) {
if (dif_r > 0) ret -= abs(dif_r) * S;
else ret += abs(dif_r) * T;
}
cout << ret << '\n';
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
364 KB |
Output is correct |
2 |
Correct |
2 ms |
492 KB |
Output is correct |
3 |
Correct |
2 ms |
492 KB |
Output is correct |
4 |
Correct |
2 ms |
492 KB |
Output is correct |
5 |
Correct |
2 ms |
492 KB |
Output is correct |
6 |
Correct |
2 ms |
492 KB |
Output is correct |
7 |
Correct |
2 ms |
492 KB |
Output is correct |
8 |
Correct |
2 ms |
492 KB |
Output is correct |
9 |
Correct |
2 ms |
492 KB |
Output is correct |
10 |
Correct |
2 ms |
492 KB |
Output is correct |
11 |
Correct |
2 ms |
492 KB |
Output is correct |
12 |
Correct |
2 ms |
492 KB |
Output is correct |
13 |
Correct |
2 ms |
492 KB |
Output is correct |
14 |
Correct |
2 ms |
492 KB |
Output is correct |
15 |
Correct |
2 ms |
492 KB |
Output is correct |
16 |
Correct |
2 ms |
492 KB |
Output is correct |
17 |
Correct |
2 ms |
512 KB |
Output is correct |
18 |
Correct |
2 ms |
492 KB |
Output is correct |
19 |
Correct |
0 ms |
364 KB |
Output is correct |
20 |
Correct |
0 ms |
364 KB |
Output is correct |
21 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
186 ms |
6508 KB |
Output is correct |
2 |
Correct |
190 ms |
7148 KB |
Output is correct |
3 |
Correct |
201 ms |
7660 KB |
Output is correct |
4 |
Correct |
184 ms |
6892 KB |
Output is correct |
5 |
Correct |
193 ms |
7660 KB |
Output is correct |
6 |
Correct |
139 ms |
8044 KB |
Output is correct |
7 |
Correct |
136 ms |
8044 KB |
Output is correct |
8 |
Correct |
180 ms |
8008 KB |
Output is correct |
9 |
Correct |
187 ms |
8300 KB |
Output is correct |
10 |
Correct |
179 ms |
7148 KB |
Output is correct |
11 |
Correct |
129 ms |
8044 KB |
Output is correct |
12 |
Correct |
134 ms |
8428 KB |
Output is correct |
13 |
Correct |
137 ms |
8952 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
364 KB |
Output is correct |
2 |
Correct |
2 ms |
492 KB |
Output is correct |
3 |
Correct |
2 ms |
492 KB |
Output is correct |
4 |
Correct |
2 ms |
492 KB |
Output is correct |
5 |
Correct |
2 ms |
492 KB |
Output is correct |
6 |
Correct |
2 ms |
492 KB |
Output is correct |
7 |
Correct |
2 ms |
492 KB |
Output is correct |
8 |
Correct |
2 ms |
492 KB |
Output is correct |
9 |
Correct |
2 ms |
492 KB |
Output is correct |
10 |
Correct |
2 ms |
492 KB |
Output is correct |
11 |
Correct |
2 ms |
492 KB |
Output is correct |
12 |
Correct |
2 ms |
492 KB |
Output is correct |
13 |
Correct |
2 ms |
492 KB |
Output is correct |
14 |
Correct |
2 ms |
492 KB |
Output is correct |
15 |
Correct |
2 ms |
492 KB |
Output is correct |
16 |
Correct |
2 ms |
492 KB |
Output is correct |
17 |
Correct |
2 ms |
512 KB |
Output is correct |
18 |
Correct |
2 ms |
492 KB |
Output is correct |
19 |
Correct |
0 ms |
364 KB |
Output is correct |
20 |
Correct |
0 ms |
364 KB |
Output is correct |
21 |
Correct |
1 ms |
364 KB |
Output is correct |
22 |
Correct |
186 ms |
6508 KB |
Output is correct |
23 |
Correct |
190 ms |
7148 KB |
Output is correct |
24 |
Correct |
201 ms |
7660 KB |
Output is correct |
25 |
Correct |
184 ms |
6892 KB |
Output is correct |
26 |
Correct |
193 ms |
7660 KB |
Output is correct |
27 |
Correct |
139 ms |
8044 KB |
Output is correct |
28 |
Correct |
136 ms |
8044 KB |
Output is correct |
29 |
Correct |
180 ms |
8008 KB |
Output is correct |
30 |
Correct |
187 ms |
8300 KB |
Output is correct |
31 |
Correct |
179 ms |
7148 KB |
Output is correct |
32 |
Correct |
129 ms |
8044 KB |
Output is correct |
33 |
Correct |
134 ms |
8428 KB |
Output is correct |
34 |
Correct |
137 ms |
8952 KB |
Output is correct |
35 |
Correct |
194 ms |
6636 KB |
Output is correct |
36 |
Correct |
195 ms |
8044 KB |
Output is correct |
37 |
Correct |
200 ms |
8812 KB |
Output is correct |
38 |
Correct |
193 ms |
8684 KB |
Output is correct |
39 |
Correct |
197 ms |
8684 KB |
Output is correct |
40 |
Correct |
191 ms |
8684 KB |
Output is correct |
41 |
Correct |
197 ms |
8428 KB |
Output is correct |
42 |
Correct |
195 ms |
8556 KB |
Output is correct |
43 |
Correct |
199 ms |
8044 KB |
Output is correct |
44 |
Correct |
196 ms |
8300 KB |
Output is correct |
45 |
Correct |
189 ms |
8172 KB |
Output is correct |
46 |
Correct |
194 ms |
8812 KB |
Output is correct |
47 |
Correct |
136 ms |
8684 KB |
Output is correct |
48 |
Correct |
147 ms |
8812 KB |
Output is correct |
49 |
Correct |
178 ms |
7916 KB |
Output is correct |
50 |
Correct |
130 ms |
8832 KB |
Output is correct |
51 |
Correct |
134 ms |
8684 KB |
Output is correct |
52 |
Correct |
135 ms |
8684 KB |
Output is correct |