#include <iostream>
#include <iomanip>
#include <cassert>
#include <vector>
#include <numeric>
#include <string>
#include <bitset>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <random>
#include <ctime>
#include <chrono>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)((x).size())
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
//typedef __int128_t int128;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const char en = '\n';
const int INF = 1e9 + 7;
const ll INFLL = 1e18;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#ifdef __APPLE__
#include "debug.h"
//#define debug(...) 42
#else
#define debug(...) 42
#endif
ll s, t;
struct SegTree {
struct Node {
ll T, l, r, pushed;
};
int n, qL, qR, index;
ll val, ans;
const ll off = 0;
vector<Node> tree;
vector<ll> a;
SegTree(int _n) {
n = _n;
tree.assign(4 * n, {0, 0, 0, off});
}
void update_vertex(int v, int l, int r) {
int m = (l + r) / 2, vL = 2 * v, vR = vL + 1;
push(vL, l, m);
push(vR, m, r);
tree[v].T = tree[vL].T + tree[vR].T;
if (tree[vL].r < tree[vR].l) {
tree[v].T -= s * (tree[vR].l - tree[vL].r);
}
else if (tree[vL].r > tree[vR].l) {
tree[v].T += t * (tree[vL].r - tree[vR].l);
}
tree[v].l = tree[vL].l;
tree[v].r = tree[vR].r;
}
void push(int v, int l, int r) {
if (tree[v].pushed == off) return;
int m = (l + r) / 2, vL = 2 * v, vR = vL + 1;
tree[v].l += tree[v].pushed;
tree[v].r += tree[v].pushed;
if (l + 1 != r) {
tree[vL].pushed += tree[v].pushed;
tree[vR].pushed += tree[v].pushed;
}
tree[v].pushed = off;
}
void build(vector<ll> &_a) {
a = _a;
build_tree(1, 0, n);
}
void build_tree(int v, int l, int r) {
if (l + 1 == r) {
tree[v] = {0, a[l], a[l], off};
return;
}
int m = (l + r) / 2, vL = 2 * v, vR = vL + 1;
build_tree(vL, l, m);
build_tree(vR, m, r);
update_vertex(v, l, r);
}
void update_segment(int _qL, int _qR, ll _val) {
qL = _qL;
qR = _qR + 1;
val = _val;
update_segment_tree(1, 0, n);
}
void update_segment_tree(int v, int l, int r) {
push(v, l, r);
if (qL <= l && r <= qR) {
tree[v].pushed += val;
push(v, l, r);
return;
}
int m = (l + r) / 2, vL = 2 * v, vR = vL + 1;
if (qL < m) update_segment_tree(vL, l, m);
if (m < qR) update_segment_tree(vR, m, r);
update_vertex(v, l, r);
}
ll get_all() {
return tree[1].T;
}
};
void solve() {
int n, q;
cin >> n >> q >> s >> t;
vector<ll> a(n + 1);
for (auto &i: a) cin >> i;
SegTree tr(n + 1);
tr.build(a);
while (q--) {
int l, r;
ll x;
cin >> l >> r >> x;
tr.update_segment(l, r, x);
cout << tr.get_all() << en;
}
}
int main() {
#ifdef __APPLE__
freopen("input.txt", "r", stdin);
#else
ios_base::sync_with_stdio(0);
cin.tie(0);
#endif
solve();
return 0;
}
Compilation message
foehn_phenomena.cpp: In member function 'void SegTree::push(int, int, int)':
foehn_phenomena.cpp:84:13: warning: unused variable 'm' [-Wunused-variable]
84 | int m = (l + r) / 2, vL = 2 * v, vR = vL + 1;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
596 KB |
Output is correct |
2 |
Correct |
2 ms |
596 KB |
Output is correct |
3 |
Correct |
3 ms |
596 KB |
Output is correct |
4 |
Correct |
2 ms |
596 KB |
Output is correct |
5 |
Correct |
3 ms |
592 KB |
Output is correct |
6 |
Correct |
3 ms |
588 KB |
Output is correct |
7 |
Correct |
2 ms |
652 KB |
Output is correct |
8 |
Correct |
2 ms |
624 KB |
Output is correct |
9 |
Correct |
4 ms |
588 KB |
Output is correct |
10 |
Correct |
2 ms |
596 KB |
Output is correct |
11 |
Correct |
3 ms |
596 KB |
Output is correct |
12 |
Correct |
4 ms |
592 KB |
Output is correct |
13 |
Correct |
2 ms |
588 KB |
Output is correct |
14 |
Correct |
2 ms |
596 KB |
Output is correct |
15 |
Correct |
3 ms |
596 KB |
Output is correct |
16 |
Correct |
3 ms |
596 KB |
Output is correct |
17 |
Correct |
2 ms |
596 KB |
Output is correct |
18 |
Correct |
2 ms |
596 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
330 ms |
35252 KB |
Output is correct |
2 |
Correct |
339 ms |
35916 KB |
Output is correct |
3 |
Correct |
381 ms |
36500 KB |
Output is correct |
4 |
Correct |
298 ms |
36020 KB |
Output is correct |
5 |
Correct |
321 ms |
37016 KB |
Output is correct |
6 |
Correct |
152 ms |
36052 KB |
Output is correct |
7 |
Correct |
170 ms |
36052 KB |
Output is correct |
8 |
Correct |
326 ms |
36884 KB |
Output is correct |
9 |
Correct |
340 ms |
37152 KB |
Output is correct |
10 |
Correct |
347 ms |
35908 KB |
Output is correct |
11 |
Correct |
148 ms |
35920 KB |
Output is correct |
12 |
Correct |
152 ms |
36764 KB |
Output is correct |
13 |
Correct |
156 ms |
36980 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
596 KB |
Output is correct |
2 |
Correct |
2 ms |
596 KB |
Output is correct |
3 |
Correct |
3 ms |
596 KB |
Output is correct |
4 |
Correct |
2 ms |
596 KB |
Output is correct |
5 |
Correct |
3 ms |
592 KB |
Output is correct |
6 |
Correct |
3 ms |
588 KB |
Output is correct |
7 |
Correct |
2 ms |
652 KB |
Output is correct |
8 |
Correct |
2 ms |
624 KB |
Output is correct |
9 |
Correct |
4 ms |
588 KB |
Output is correct |
10 |
Correct |
2 ms |
596 KB |
Output is correct |
11 |
Correct |
3 ms |
596 KB |
Output is correct |
12 |
Correct |
4 ms |
592 KB |
Output is correct |
13 |
Correct |
2 ms |
588 KB |
Output is correct |
14 |
Correct |
2 ms |
596 KB |
Output is correct |
15 |
Correct |
3 ms |
596 KB |
Output is correct |
16 |
Correct |
3 ms |
596 KB |
Output is correct |
17 |
Correct |
2 ms |
596 KB |
Output is correct |
18 |
Correct |
2 ms |
596 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
22 |
Correct |
330 ms |
35252 KB |
Output is correct |
23 |
Correct |
339 ms |
35916 KB |
Output is correct |
24 |
Correct |
381 ms |
36500 KB |
Output is correct |
25 |
Correct |
298 ms |
36020 KB |
Output is correct |
26 |
Correct |
321 ms |
37016 KB |
Output is correct |
27 |
Correct |
152 ms |
36052 KB |
Output is correct |
28 |
Correct |
170 ms |
36052 KB |
Output is correct |
29 |
Correct |
326 ms |
36884 KB |
Output is correct |
30 |
Correct |
340 ms |
37152 KB |
Output is correct |
31 |
Correct |
347 ms |
35908 KB |
Output is correct |
32 |
Correct |
148 ms |
35920 KB |
Output is correct |
33 |
Correct |
152 ms |
36764 KB |
Output is correct |
34 |
Correct |
156 ms |
36980 KB |
Output is correct |
35 |
Correct |
345 ms |
35420 KB |
Output is correct |
36 |
Correct |
330 ms |
36808 KB |
Output is correct |
37 |
Correct |
328 ms |
37720 KB |
Output is correct |
38 |
Correct |
303 ms |
37420 KB |
Output is correct |
39 |
Correct |
327 ms |
37460 KB |
Output is correct |
40 |
Correct |
351 ms |
37420 KB |
Output is correct |
41 |
Correct |
315 ms |
37300 KB |
Output is correct |
42 |
Correct |
296 ms |
37444 KB |
Output is correct |
43 |
Correct |
454 ms |
36608 KB |
Output is correct |
44 |
Correct |
308 ms |
37068 KB |
Output is correct |
45 |
Correct |
325 ms |
37068 KB |
Output is correct |
46 |
Correct |
340 ms |
38244 KB |
Output is correct |
47 |
Correct |
165 ms |
36684 KB |
Output is correct |
48 |
Correct |
140 ms |
36688 KB |
Output is correct |
49 |
Correct |
294 ms |
35788 KB |
Output is correct |
50 |
Correct |
188 ms |
36532 KB |
Output is correct |
51 |
Correct |
153 ms |
37148 KB |
Output is correct |
52 |
Correct |
228 ms |
36812 KB |
Output is correct |