#include <bits/stdc++.h>
#define int long long
using namespace std;
struct bit
{
vector<int> b;
int sz;
void resize(int n)
{
/*sz = n;
b = vector<int>(n + 2);*/
}
void update(int pos, int val)
{
//assert(pos >= 1 && pos <= sz);
/*int n = (int)b.size() - 1;
for (int i = pos; i <= n; i += i & (-i))
{
b[i] += val;
}*/
}
int query(int pos)
{
//assert(pos >= 1 && pos <= sz);
/*int ans = 0;
for (int i = pos; i; i -= i & (-i))
{
ans += b[i];
}
return ans;*/
return 0;
}
void update(int st, int dr, int val)
{
//assert(st <= dr && st >= 1 && dr <= sz);
//update(st, val);
//update(dr + 1, -val);
}
};
struct rmq
{
vector<vector<pair<int, int>>> rmq;
vector<int> lg;
void build(vector<int> a, int n)
{
lg = vector<int>(n + 1);
for (int i = 2; i <= n; ++i)
{
lg[i] = lg[i / 2] + 1;
}
rmq = vector<vector<pair<int, int>>>(n + 1, vector<pair<int, int>>(lg[n] + 1));
for (int i = 1; i <= n; ++i)
{
rmq[i][0] = {a[i], i};
}
for (int j = 1; j <= lg[n]; ++j)
{
for (int i = 1; i + (1 << j) - 1 <= n; ++i)
{
rmq[i][j] = min(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
}
}
}
pair<int, int> query(int st, int dr)
{
int pow_2 = lg[dr - st + 1];
return min(rmq[st][pow_2], rmq[dr - (1 << pow_2) + 1][pow_2]);
}
};
struct cartesian
{
vector<int> a;
vector<vector<int>> g;
vector<vector<pair<int, int>>> stars;
vector<vector<int>> jump;
vector<int> tin;
vector<int> tout;
vector<int> dp;
int p;
int root;
int max_jump;
int n;
void build(vector<int> _a, int _n)
{
n = _n;
a = _a;
dp = tin = tout = vector<int>(n + 1);
g = vector<vector<int>>(n + 1);
rmq t;
t.build(a, n);
max_jump = t.lg[n];
jump = vector<vector<int>>(n + 1, vector<int>(max_jump + 1));
stars = vector<vector<pair<int, int>>>(n + 1);
function<void(int, int, int)> construct = [&](int st, int dr, int parent)
{
pair<int, int> qui = t.query(st, dr);
if (parent != 0)
{
g[parent].push_back(qui.second);
g[qui.second].push_back(parent);
jump[qui.second][0] = parent;
}
else
{
jump[qui.second][0] = qui.second;
root = qui.second;
}
for (int i = 1; i <= max_jump; ++i)
{
jump[qui.second][i] = jump[jump[qui.second][i - 1]][i - 1];
}
tin[qui.second] = ++p;
if (qui.second != st)
{
construct(st, qui.second - 1, qui.second);
}
if (qui.second != dr)
{
construct(qui.second + 1, dr, qui.second);
}
tout[qui.second] = ++p;
};
construct(1, n, 0);
}
void insert(int node, int h, int coef)
{
int qui = node;
for (int i = max_jump; i >= 0; --i)
{
if (a[jump[node][i]] >= h)
{
node = jump[node][i];
}
}
stars[node].push_back({qui, coef});
}
int solve()
{
bit tree;
bit tree2;
tree.resize(p);
tree2.resize(p);
function<void(int, int)> dfs = [&](int node, int parent)
{
for (auto i : g[node])
{
if (i != parent)
{
dfs(i, node);
}
}
int sum = 0;
for (auto i : g[node])
{
if (i != parent)
{
sum += dp[i];
}
}
tree.update(tin[node], tout[node], sum);
dp[node] = sum;
for (auto chain : stars[node])
{
dp[node] = max(dp[node], chain.second + tree.query(tin[chain.first]) - tree2.query(tin[chain.first]));
}
tree2.update(tin[node], tout[node], dp[node]);
};
dfs(root, 0);
return dp[root];
//return dp[root];
}
};
int32_t main()
{
cin.tie(nullptr)->sync_with_stdio(false);
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; ++i)
{
cin >> a[i];
a[i] = n - a[i];
}
cartesian t;
t.build(a, n);
int m;
cin >> m;
int sum = 0;
for (int i = 1; i <= m; ++i)
{
int qui, wh, coef;
cin >> qui >> wh >> coef;
wh = n - wh + 1;
sum += coef;
t.insert(qui, wh, coef);
}
cout << sum - t.solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
