#include <bits/stdc++.h>
using namespace std;
namespace Fenwick {
int n;
vector<int64_t> tree;
void Init(int n_) {
n = n_;
tree.assign(n + 1, 0);
}
void Add(int pos, int64_t val) {
for (++pos; pos <= n; pos += pos & -pos)
tree[pos] += val;
}
void Add(int left, int right, int64_t val) {
Add(left, val);
if (right + 1 < n)
Add(right + 1, -val);
}
int64_t Query(int pos) {
int64_t res = 0;
for (++pos; pos > 0; pos -= pos & -pos)
res += tree[pos];
return res;
}
}
namespace DSU {
int n;
vector<int> dad, sz, lft, rgt;
vector<int64_t> dp;
void Init(int n_) {
n = n_;
dad.resize(n), sz.resize(n), lft.resize(n), rgt.resize(n), dp.resize(n);
for (int i = 0; i < n; ++i) {
lft[i] = rgt[i] = i;
dad[i] = -1;
sz[i] = 1;
dp[i] = 0;
}
}
int Find(int x) {
if (dad[x] == -1) return x;
return dad[x] = Find(dad[x]);
}
void Union(int x, int y) {
x = Find(x), y = Find(y);
if (x == y) return;
if (sz[x] < sz[y]) swap(x, y);
sz[x] += sz[y];
dad[y] = x;
Fenwick::Add(lft[x], rgt[x], dp[y]);
Fenwick::Add(lft[y], rgt[y], dp[x]);
dp[x] += dp[y];
lft[x] = min(lft[x], lft[y]);
rgt[x] = max(rgt[x], rgt[y]);
}
void Update(int x, int64_t val) {
x = Find(x);
dp[x] = max(dp[x], val);
}
int64_t Get(int node) {
return dp[Find(node)];
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n; cin >> n;
vector<int> h(n);
vector<vector<int>> walls(n + 1);
for (int i = 0; i < n; ++i) {
cin >> h[i];
walls[h[i]].emplace_back(i);
}
int m; cin >> m;
vector<vector<pair<int, int>>> stars(n + 1);
int64_t ans = 0;
for (int i = 0; i < m; ++i) {
int x, y, c; cin >> x >> y >> c; --x, --y;
stars[y].emplace_back(x, c);
ans += c;
}
DSU::Init(n);
Fenwick::Init(n);
for (int y = 0; y <= n; ++y) {
for (int &x : walls[y]) {
if (x - 1 >= 0 && h[x - 1] <= y) {
DSU::Union(x - 1, x);
}
if (x + 1 < n && h[x + 1] <= y) {
DSU::Union(x, x + 1);
}
}
for (auto &star : stars[y]) {
int x, c; tie(x, c) = star;
DSU::Update(x, c + Fenwick::Query(x));
}
}
for (int i = 1; i < n; ++i) {
DSU::Union(i - 1, i);
}
cout << ans - DSU::Get(0) << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
384 KB |
Output is correct |
11 |
Correct |
5 ms |
384 KB |
Output is correct |
12 |
Correct |
5 ms |
384 KB |
Output is correct |
13 |
Correct |
5 ms |
384 KB |
Output is correct |
14 |
Correct |
5 ms |
384 KB |
Output is correct |
15 |
Correct |
5 ms |
384 KB |
Output is correct |
16 |
Correct |
5 ms |
384 KB |
Output is correct |
17 |
Correct |
5 ms |
384 KB |
Output is correct |
18 |
Correct |
5 ms |
384 KB |
Output is correct |
19 |
Correct |
5 ms |
384 KB |
Output is correct |
20 |
Correct |
5 ms |
384 KB |
Output is correct |
21 |
Correct |
5 ms |
384 KB |
Output is correct |
22 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
384 KB |
Output is correct |
11 |
Correct |
5 ms |
384 KB |
Output is correct |
12 |
Correct |
5 ms |
384 KB |
Output is correct |
13 |
Correct |
5 ms |
384 KB |
Output is correct |
14 |
Correct |
5 ms |
384 KB |
Output is correct |
15 |
Correct |
5 ms |
384 KB |
Output is correct |
16 |
Correct |
5 ms |
384 KB |
Output is correct |
17 |
Correct |
5 ms |
384 KB |
Output is correct |
18 |
Correct |
5 ms |
384 KB |
Output is correct |
19 |
Correct |
5 ms |
384 KB |
Output is correct |
20 |
Correct |
5 ms |
384 KB |
Output is correct |
21 |
Correct |
5 ms |
384 KB |
Output is correct |
22 |
Correct |
5 ms |
384 KB |
Output is correct |
23 |
Correct |
6 ms |
512 KB |
Output is correct |
24 |
Correct |
6 ms |
512 KB |
Output is correct |
25 |
Correct |
6 ms |
512 KB |
Output is correct |
26 |
Correct |
6 ms |
512 KB |
Output is correct |
27 |
Correct |
6 ms |
512 KB |
Output is correct |
28 |
Correct |
8 ms |
512 KB |
Output is correct |
29 |
Correct |
6 ms |
512 KB |
Output is correct |
30 |
Correct |
6 ms |
512 KB |
Output is correct |
31 |
Correct |
6 ms |
512 KB |
Output is correct |
32 |
Correct |
6 ms |
640 KB |
Output is correct |
33 |
Correct |
6 ms |
640 KB |
Output is correct |
34 |
Correct |
6 ms |
640 KB |
Output is correct |
35 |
Correct |
6 ms |
640 KB |
Output is correct |
36 |
Correct |
6 ms |
512 KB |
Output is correct |
37 |
Correct |
6 ms |
512 KB |
Output is correct |
38 |
Correct |
6 ms |
640 KB |
Output is correct |
39 |
Correct |
6 ms |
512 KB |
Output is correct |
40 |
Correct |
6 ms |
512 KB |
Output is correct |
41 |
Correct |
6 ms |
512 KB |
Output is correct |
42 |
Correct |
6 ms |
512 KB |
Output is correct |
43 |
Correct |
6 ms |
512 KB |
Output is correct |
44 |
Correct |
6 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
384 KB |
Output is correct |
11 |
Correct |
5 ms |
384 KB |
Output is correct |
12 |
Correct |
5 ms |
384 KB |
Output is correct |
13 |
Correct |
5 ms |
384 KB |
Output is correct |
14 |
Correct |
5 ms |
384 KB |
Output is correct |
15 |
Correct |
5 ms |
384 KB |
Output is correct |
16 |
Correct |
5 ms |
384 KB |
Output is correct |
17 |
Correct |
5 ms |
384 KB |
Output is correct |
18 |
Correct |
5 ms |
384 KB |
Output is correct |
19 |
Correct |
5 ms |
384 KB |
Output is correct |
20 |
Correct |
5 ms |
384 KB |
Output is correct |
21 |
Correct |
5 ms |
384 KB |
Output is correct |
22 |
Correct |
5 ms |
384 KB |
Output is correct |
23 |
Correct |
6 ms |
512 KB |
Output is correct |
24 |
Correct |
6 ms |
512 KB |
Output is correct |
25 |
Correct |
6 ms |
512 KB |
Output is correct |
26 |
Correct |
6 ms |
512 KB |
Output is correct |
27 |
Correct |
6 ms |
512 KB |
Output is correct |
28 |
Correct |
8 ms |
512 KB |
Output is correct |
29 |
Correct |
6 ms |
512 KB |
Output is correct |
30 |
Correct |
6 ms |
512 KB |
Output is correct |
31 |
Correct |
6 ms |
512 KB |
Output is correct |
32 |
Correct |
6 ms |
640 KB |
Output is correct |
33 |
Correct |
6 ms |
640 KB |
Output is correct |
34 |
Correct |
6 ms |
640 KB |
Output is correct |
35 |
Correct |
6 ms |
640 KB |
Output is correct |
36 |
Correct |
6 ms |
512 KB |
Output is correct |
37 |
Correct |
6 ms |
512 KB |
Output is correct |
38 |
Correct |
6 ms |
640 KB |
Output is correct |
39 |
Correct |
6 ms |
512 KB |
Output is correct |
40 |
Correct |
6 ms |
512 KB |
Output is correct |
41 |
Correct |
6 ms |
512 KB |
Output is correct |
42 |
Correct |
6 ms |
512 KB |
Output is correct |
43 |
Correct |
6 ms |
512 KB |
Output is correct |
44 |
Correct |
6 ms |
512 KB |
Output is correct |
45 |
Correct |
236 ms |
24324 KB |
Output is correct |
46 |
Correct |
237 ms |
23928 KB |
Output is correct |
47 |
Correct |
250 ms |
23672 KB |
Output is correct |
48 |
Correct |
228 ms |
24312 KB |
Output is correct |
49 |
Correct |
234 ms |
23544 KB |
Output is correct |
50 |
Correct |
233 ms |
23544 KB |
Output is correct |
51 |
Correct |
228 ms |
23672 KB |
Output is correct |
52 |
Correct |
226 ms |
24056 KB |
Output is correct |
53 |
Correct |
232 ms |
24056 KB |
Output is correct |
54 |
Correct |
187 ms |
26616 KB |
Output is correct |
55 |
Correct |
190 ms |
26104 KB |
Output is correct |
56 |
Correct |
180 ms |
25848 KB |
Output is correct |
57 |
Correct |
182 ms |
25592 KB |
Output is correct |
58 |
Correct |
162 ms |
20732 KB |
Output is correct |
59 |
Correct |
171 ms |
20600 KB |
Output is correct |
60 |
Correct |
155 ms |
26236 KB |
Output is correct |
61 |
Correct |
138 ms |
19960 KB |
Output is correct |
62 |
Correct |
187 ms |
23416 KB |
Output is correct |
63 |
Correct |
139 ms |
19428 KB |
Output is correct |
64 |
Correct |
148 ms |
19448 KB |
Output is correct |
65 |
Correct |
180 ms |
23676 KB |
Output is correct |
66 |
Correct |
140 ms |
19056 KB |
Output is correct |