#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
using ll = long long;
const int nbit = 17, nmax = 2e5 + 5;
#define lsb(x) (x & -x)
struct AIB {
vector<ll> tree; int len;
void init(int n) {
len = n;
tree.clear(), tree.resize(n + 1, 0);
}
void upd(int x, int val) {
while(x <= len)
tree[x] += val,
x += lsb(x);
return;
}
void upd(int l, int r, int val) {
upd(l, val);
upd(r + 1, -val);
}
int query(int x) {
int sum = 0;
while(x > 0) sum += tree[x], x -= lsb(x);
return sum;
}
};
int n, m;
namespace CartTree {
vector<int> g[nmax];
vector<pii> atrendpoint[nmax];
int p[nmax][nbit], lson[nmax], rson[nmax], pin[nmax], pout[nmax], inp = 1;
static int root;
vector<int> v;
ll dp[nmax], son[nmax];
AIB pinexsum;
void build(vector<int> abogus) {
v = move(abogus);
root = 0;
for(int i = 0; i < n; i++) { //init carttree
int lst = i - 1, lastval = -1;
lson[i] = rson[i] = -1;
while(lst >= 0 && v[lst] <= v[i])
lastval = lst,
lst = p[lst][0];
p[i][0] = lst;
lson[i] = lastval;
if(lastval != -1)
p[lastval][0] = i;
if(lst != -1)
rson[lst] = i;
}
for(int i = 0; i < n; i++) { // init tree
if(lson[i] != -1)
g[i].push_back(lson[i]),
p[lson[i]][0] = i;
if(rson[i] != -1)
g[i].push_back(rson[i]),
p[lson[i]][0] = i;
if(p[i][0] == -1)
root = i;
}
p[root][0] = root;
for(int step = 1; step < nbit; step++)
for(int i = 0; i < n; i++)
p[i][step] = p[p[i][step - 1]][step - 1];
auto dfs = [&](auto &&self, int node) -> void {
pin[node] = inp++;
for(auto x : g[node])
self(self, x);
pout[node] = inp - 1;
};
dfs(dfs, root);
pinexsum.init(n + 1);
}
void addstar(int x, int height, int cost) {
int temp = x;
for(int i = nbit - 1; i >= 0; i--) {
if(v[p[x][i]] < height)
x = p[x][i];
}
atrendpoint[x].emplace_back(temp, cost);
}
void startdp(int node = root) {
for(auto x : g[node])
startdp(x),
son[node] += dp[x];
dp[node] = son[node];
pinexsum.upd(pin[node], pout[node], son[node]);
for(auto [x, cost] : atrendpoint[node])
dp[node] = max(dp[node], (ll)cost + pinexsum.query(pin[x]));
pinexsum.upd(pin[node], pout[node], -dp[node]);
}
}
int main() {
cin >> n;
vector<int> heights(n);
for(auto &x : heights)
cin >> x;
CartTree::build(heights);
cin >> m;
ll sum = 0;
for(int i = 0, x, y, c; i < m; i++) {
cin >> x >> y >> c;
CartTree::addstar(x - 1, y, c);
sum += c;
}
CartTree::startdp();
cout << sum - CartTree::dp[CartTree::root] << '\n';
}
/*
*
* 6 A 8 x 5
* x x x x
* x x x x x
* x x x x x
* x x 7 x x x x
* x x x x x x x
* x x x x x x x
*
*
*/
Compilation message
constellation3.cpp: In function 'void CartTree::startdp(int)':
constellation3.cpp:97:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
97 | for(auto [x, cost] : atrendpoint[node])
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
9796 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
9684 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
9796 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
9684 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
9796 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
9684 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
