#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define kill(x) cout << x << endl, exit(0);
#define endl "\n"
using namespace std;
typedef long long ll;
typedef long double ld;
const int MAXN = (int)1e6 + 7;
const int MOD = (int)1e9 + 7;
const ll INF = (ll)1e18 + 7;
int n, m, q, tmp, tmp2, tmp3, tmp4, ans, k, u, v, w, flag;
int arr[MAXN], A, B, U, D;
/* Segment Tree */
#define mid ((l+r)>>1)
#define lid (id<<1)
#define rid (lid|1)
int seg[MAXN<<2], lazy[MAXN<<2];
inline void relax(int l, int r, int id) {
if (lazy[id] == 0) return;
seg[lid] += lazy[id]; seg[rid] += lazy[id];
lazy[lid] += lazy[id]; lazy[rid] += lazy[id];
lazy[id] = 0;
}
void build(int l=0, int r=n, int id=1) {
if (l+1 == r) {
seg[id] = arr[l];
return;
}
build(l, mid, lid);
build(mid, r, rid);
seg[id] = seg[lid]+seg[rid];
}
void upd(int s, int t, int x, int l=0, int r=n, int id=1) {
if (s >= t) return;
if (s <= l && t >= r) {
seg[id] += x;
lazy[id] += x;
return;
}
relax(l, r, id);
if (s < mid) upd(s, t, x, l, mid, lid);
if (t > mid) upd(s, t, x, mid, r, rid);
seg[id] = seg[lid]+seg[rid];
}
int get(int x, int l=0, int r=n, int id=1) {
if (l+1 == r) return seg[id];
relax(l, r, id);
if (x < mid) return get(x, l, mid, lid);
return get(x, mid, r, rid);
}
/* Segment Tree */
inline void f(int u, int v, int x) {
if (u < v) U += (v-u)*x;
else D += (u-v)*x;
}
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> q >> A >> B; n++;
for (int i=0; i<n; i++) {
cin >> arr[i];
if (i) f(arr[i-1], arr[i], 1);
}
build();
while (q--) {
cin >> u >> v >> w;
f(get(u-1), get(u), -1);
if (v != n-1) f(get(v), get(v+1), -1);
upd(u, v+1, w);
f(get(u-1), get(u), 1);
if (v != n-1) f(get(v), get(v+1), 1);
// cout << "!";
cout << D*B-U*A << endl;
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4440 KB |
Output is correct |
2 |
Correct |
3 ms |
4444 KB |
Output is correct |
3 |
Correct |
3 ms |
4660 KB |
Output is correct |
4 |
Correct |
3 ms |
4444 KB |
Output is correct |
5 |
Correct |
3 ms |
4444 KB |
Output is correct |
6 |
Correct |
3 ms |
4444 KB |
Output is correct |
7 |
Correct |
3 ms |
4444 KB |
Output is correct |
8 |
Correct |
3 ms |
4444 KB |
Output is correct |
9 |
Correct |
3 ms |
4444 KB |
Output is correct |
10 |
Correct |
3 ms |
4444 KB |
Output is correct |
11 |
Correct |
3 ms |
4444 KB |
Output is correct |
12 |
Correct |
3 ms |
4444 KB |
Output is correct |
13 |
Correct |
2 ms |
4444 KB |
Output is correct |
14 |
Correct |
2 ms |
4444 KB |
Output is correct |
15 |
Correct |
3 ms |
4444 KB |
Output is correct |
16 |
Correct |
2 ms |
4444 KB |
Output is correct |
17 |
Correct |
2 ms |
4444 KB |
Output is correct |
18 |
Correct |
3 ms |
4440 KB |
Output is correct |
19 |
Correct |
1 ms |
4444 KB |
Output is correct |
20 |
Correct |
1 ms |
4444 KB |
Output is correct |
21 |
Correct |
1 ms |
4476 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
290 ms |
20776 KB |
Output is correct |
2 |
Correct |
281 ms |
21648 KB |
Output is correct |
3 |
Correct |
288 ms |
22212 KB |
Output is correct |
4 |
Correct |
271 ms |
21072 KB |
Output is correct |
5 |
Correct |
288 ms |
22392 KB |
Output is correct |
6 |
Correct |
122 ms |
17488 KB |
Output is correct |
7 |
Correct |
107 ms |
17488 KB |
Output is correct |
8 |
Correct |
256 ms |
22356 KB |
Output is correct |
9 |
Correct |
227 ms |
22608 KB |
Output is correct |
10 |
Correct |
229 ms |
21664 KB |
Output is correct |
11 |
Correct |
123 ms |
17532 KB |
Output is correct |
12 |
Correct |
107 ms |
17744 KB |
Output is correct |
13 |
Correct |
105 ms |
18260 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4440 KB |
Output is correct |
2 |
Correct |
3 ms |
4444 KB |
Output is correct |
3 |
Correct |
3 ms |
4660 KB |
Output is correct |
4 |
Correct |
3 ms |
4444 KB |
Output is correct |
5 |
Correct |
3 ms |
4444 KB |
Output is correct |
6 |
Correct |
3 ms |
4444 KB |
Output is correct |
7 |
Correct |
3 ms |
4444 KB |
Output is correct |
8 |
Correct |
3 ms |
4444 KB |
Output is correct |
9 |
Correct |
3 ms |
4444 KB |
Output is correct |
10 |
Correct |
3 ms |
4444 KB |
Output is correct |
11 |
Correct |
3 ms |
4444 KB |
Output is correct |
12 |
Correct |
3 ms |
4444 KB |
Output is correct |
13 |
Correct |
2 ms |
4444 KB |
Output is correct |
14 |
Correct |
2 ms |
4444 KB |
Output is correct |
15 |
Correct |
3 ms |
4444 KB |
Output is correct |
16 |
Correct |
2 ms |
4444 KB |
Output is correct |
17 |
Correct |
2 ms |
4444 KB |
Output is correct |
18 |
Correct |
3 ms |
4440 KB |
Output is correct |
19 |
Correct |
1 ms |
4444 KB |
Output is correct |
20 |
Correct |
1 ms |
4444 KB |
Output is correct |
21 |
Correct |
1 ms |
4476 KB |
Output is correct |
22 |
Correct |
290 ms |
20776 KB |
Output is correct |
23 |
Correct |
281 ms |
21648 KB |
Output is correct |
24 |
Correct |
288 ms |
22212 KB |
Output is correct |
25 |
Correct |
271 ms |
21072 KB |
Output is correct |
26 |
Correct |
288 ms |
22392 KB |
Output is correct |
27 |
Correct |
122 ms |
17488 KB |
Output is correct |
28 |
Correct |
107 ms |
17488 KB |
Output is correct |
29 |
Correct |
256 ms |
22356 KB |
Output is correct |
30 |
Correct |
227 ms |
22608 KB |
Output is correct |
31 |
Correct |
229 ms |
21664 KB |
Output is correct |
32 |
Correct |
123 ms |
17532 KB |
Output is correct |
33 |
Correct |
107 ms |
17744 KB |
Output is correct |
34 |
Correct |
105 ms |
18260 KB |
Output is correct |
35 |
Correct |
287 ms |
20932 KB |
Output is correct |
36 |
Correct |
284 ms |
22236 KB |
Output is correct |
37 |
Correct |
278 ms |
23092 KB |
Output is correct |
38 |
Correct |
294 ms |
22984 KB |
Output is correct |
39 |
Correct |
284 ms |
22908 KB |
Output is correct |
40 |
Correct |
291 ms |
22820 KB |
Output is correct |
41 |
Correct |
277 ms |
22608 KB |
Output is correct |
42 |
Correct |
283 ms |
22864 KB |
Output is correct |
43 |
Correct |
277 ms |
22096 KB |
Output is correct |
44 |
Correct |
284 ms |
22400 KB |
Output is correct |
45 |
Correct |
272 ms |
22356 KB |
Output is correct |
46 |
Correct |
288 ms |
23244 KB |
Output is correct |
47 |
Correct |
106 ms |
17976 KB |
Output is correct |
48 |
Correct |
112 ms |
18196 KB |
Output is correct |
49 |
Correct |
266 ms |
21432 KB |
Output is correct |
50 |
Correct |
131 ms |
18096 KB |
Output is correct |
51 |
Correct |
106 ms |
17984 KB |
Output is correct |
52 |
Correct |
151 ms |
17976 KB |
Output is correct |