#include<bits/stdc++.h>
using namespace std;
#define int 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_[400 * N], a[N], ri_[400 * N], tree[400 * N], lazy[400 * N], cur, root[N], f[N], p[N], n;
vector<pii> comp[N];
void push(int u,int l,int r) {
if(!lazy[u]) return;
tree[u] += lazy[u];
if(l != r) {
lazy[le_[u]] += lazy[u];
lazy[ri_[u]] += lazy[u];
}
lazy[u] = 0;
}
void UPD(int u) {
if(!le_[u]) le_[u] = ++cur;
if(!ri_[u]) ri_[u] = ++cur;
}
void upd(int u, int st, int en, int l, int r, int v) {
UPD(u);
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[le_[u]], tree[ri_[u]]);
}
void upd(int u,int id, int l,int r,int v) {
UPD(u);
push(u, l, r);
if(l > id || r < id) return;
if(l == r) {
tree[u] = max(tree[u], v);
return;
}
int mid = (l + r) / 2;
upd(le_[u], id, l, mid, v); upd(ri_[u], id, mid + 1, r, v);
tree[u] = max(tree[le_[u]], tree[ri_[u]]);
}
int get(int u, int st, int en, int l,int r) {
if(!u) return 0;
UPD(u);
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);
assert(u != v);
if(comp[v].size() > comp[u].size()) swap(u, v);
p[v] = u;
int 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]);
}
// cout << tree[root[u]] << " ? " << endl;
}
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;
int 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(long long int, long long int, long long int)':
constellation3.cpp:74:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for(int i = 0; i < comp[v].size(); i++) {
| ~~^~~~~~~~~~~~~~~~
constellation3.cpp: At global scope:
constellation3.cpp:82:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
82 | main() {
| ^~~~
constellation3.cpp: In function 'int main()':
constellation3.cpp:102:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | for(int j = 0; j < comp[i].size(); j++)
| ~~^~~~~~~~~~~~~~~~
constellation3.cpp:107:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | for(int i = 0; i < h.size(); i++) {
| ~~^~~~~~~~~~
/tmp/ccKOL4EM.o: in function `main':
constellation3.cpp:(.text.startup+0x10): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/10/libstdc++.a(globals_io.o)
constellation3.cpp:(.text.startup+0xa2): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/10/libstdc++.a(globals_io.o)
constellation3.cpp:(.text.startup+0xde): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/10/libstdc++.a(globals_io.o)
constellation3.cpp:(.text.startup+0x13c): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/10/libstdc++.a(globals_io.o)
constellation3.cpp:(.text.startup+0x34d): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cout' defined in .bss._ZSt4cout section in /usr/lib/gcc/x86_64-linux-gnu/10/libstdc++.a(globals_io.o)
/tmp/ccKOL4EM.o: in function `_GLOBAL__sub_I_t':
constellation3.cpp:(.text.startup+0x3fb): relocation truncated to fit: R_X86_64_PC32 against `.bss'
constellation3.cpp:(.text.startup+0x415): relocation truncated to fit: R_X86_64_PC32 against `.bss'
/usr/lib/gcc/x86_64-linux-gnu/10/libstdc++.a(vterminate.o): in function `__gnu_cxx::__verbose_terminate_handler()':
(.text._ZN9__gnu_cxx27__verbose_terminate_handlerEv+0x1e): relocation truncated to fit: R_X86_64_PC32 against `.bss._ZZN9__gnu_cxx27__verbose_terminate_handlerEvE11terminating'
(.text._ZN9__gnu_cxx27__verbose_terminate_handlerEv+0x2b): relocation truncated to fit: R_X86_64_PC32 against `.bss._ZZN9__gnu_cxx27__verbose_terminate_handlerEvE11terminating'
/usr/bin/ld: failed to convert GOTPCREL relocation; relink with --no-relax
collect2: error: ld returned 1 exit status
