#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define endl "\n"
const int N = 2e5 + 5, mod = 1e9 + 7; //!
int t, le_[200 * N], a[N], ri_[200 * N], cn[200 * N], cur, root[N], f[N], p[N], n;
vector<pii> comp[N];
ll tree[200 * N], lazy[200 * N];
void push(int u, int l,int r) {
if(!lazy[u]) return;
tree[u] += lazy[u];
if(l != r) {
if(le_[u]) lazy[le_[u]] += lazy[u];
if(ri_[u]) lazy[ri_[u]] += lazy[u];
}
lazy[u] = 0;
}
void upd(int u, int st, int en, int l,int r, ll v) {
if(!cn[u]) return;
push(u, l, r);
if(l > en || r < st) return;
if(st <= l && r <= en) {
lazy[u] = v;
push(u, l, r);
return;
}
int mid = (l + r) / 2;
upd(le_[u], st, en, l, mid, v); upd(ri_[u], st, en, mid + 1, r, v);
tree[u] = max(tree[2 * u], tree[2 * u + 1]);
}
void upd(int u, int id, int l, int r, ll v) {
if(!u) return;
push(u, l, r);
if(l > id || r < id) return;
if(l == r) {
tree[u] = max(tree[u], v);
cn[u] = 1;
return;
}
int mid = (l + r) / 2;
if(id <= mid) {
if(!le_[u]) le_[u] = ++cur;
} else if(!ri_[u]) ri_[u] = ++cur;
upd(le_[u], id, l, mid, v); upd(ri_[u], id, mid + 1, r, v);
tree[u] = max(tree[le_[u]], tree[ri_[u]]);
cn[u] = cn[le_[u]] + cn[ri_[u]];
}
ll get(int u, int st, int en, int l,int r) {
if(!cn[u]) return 0;
push(u, l, r);
if(l > en || r < st) return 0;
if(st <= l && r <= en) return tree[u];
int mid = (l + r) / 2;
return max(get(le_[u], st, en, l, mid), get(ri_[u], st, en, mid + 1, r));
}
int find(int u) {
return (p[u] == u ? p[u] : p[u] = find(p[u]));
}
void merge(int u, int v, int H) {
u = find(u); v = find(v);
if(u == v) return;
if(comp[v].size() > comp[u].size()) swap(u, v);
p[v] = u;
ll ul = get(root[u], 1, H, 1, n), vl = get(root[v], 1, H, 1, n);
upd(root[u], 1, n, 1, n, vl);
for(int i = 0; i < comp[v].size(); i++) {
if(comp[v][i].f <= H) continue;
upd(root[u], comp[v][i].f, 1, n, get(root[v], 1, comp[v][i].f, 1, n) + ul);
comp[u].push_back(comp[v][i]);
}
comp[v].clear();
}
main() {
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int m;
cin >> n;
vector<pii> h;
for(int i = 1; i <= n; i++) {
cin >> a[i];
h.push_back({a[i], i});
}
cin >> m;
ll call = 0;
while(m--) {
int x, y, w;
cin >> x >> y >> w;
comp[x].push_back({y, w});
call += w;
}
for(int i = 1; i <= n; i++) {
p[i] = i;
root[i] = ++cur;
for(int j = 0; j < comp[i].size(); j++)
upd(root[i], comp[i][j].f, 1, n, comp[i][j].s);
}
sort(h.begin(), h.end());
for(int i = 0; i < h.size(); i++) {
int id = h[i].s, H = h[i].f;
if(f[id - 1]) merge(id - 1, id, H);
if(f[id + 1]) merge(id + 1, id, H);
f[id] = 1;
}
cout << call - tree[root[find(1)]];
}
Compilation message
constellation3.cpp: In function 'void merge(int, int, int)':
constellation3.cpp:73:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for(int i = 0; i < comp[v].size(); i++) {
| ~~^~~~~~~~~~~~~~~~
constellation3.cpp: At global scope:
constellation3.cpp:81:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
81 | main() {
| ^~~~
constellation3.cpp: In function 'int main()':
constellation3.cpp:101:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | for(int j = 0; j < comp[i].size(); j++)
| ~~^~~~~~~~~~~~~~~~
constellation3.cpp:106:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | for(int i = 0; i < h.size(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
