#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define ALL(x) (x).begin(), (x).end()
#define __Dennis_Tran___ signed main()
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
using namespace std;
const int maxN = 2e5 + 5;
int n, a[maxN];
int p[20][maxN];
int tin[maxN], tout[maxN], timer;
long long dp[maxN];
vector <int> ke[maxN];
vector <pair <int, int>> stars[maxN];
struct rmq{
int f[20][maxN];
int Max(int x, int y) {return a[x] >= a[y] ? x : y;}
int get(int l, int r) {
int k = __lg(r - l + 1);
return Max(f[k][l], f[k][r - (1 << k) + 1]);
}
void build() {
FOR(i, 1, n) f[0][i] = i;
for (int i = 1; (1 << i) <= n; i++)
for (int j = 1; j <= n - (1 << i) + 1; j++)
f[i][j] = Max(f[i - 1][j], f[i - 1][j + (1 << i - 1)]);
}
} RMQ;
int build_Tree(int l, int r, int parent = 0) {
if (l > r) return 0;
int mid = RMQ.get(l, r);
tin[mid] = ++timer;
ke[parent].emplace_back(mid);
p[0][mid] = parent;
FOR(i, 1, 18) p[i][mid] = p[i - 1][p[i - 1][mid]];
build_Tree(l, mid - 1, mid);
build_Tree(mid + 1, r, mid);
tout[mid] = timer;
return mid;
}
struct BIT{
long long bit[maxN];
void update(int x, long long val) {
for (; x <= n; x += x&-x) bit[x] += val;
}
void update(int l, int r, long long val) {
update(l, val);
update(r + 1, - val);
}
long long get(int x) {
long long ans = 0;
for (; x; x -= x&-x) ans += bit[x];
return ans;
}
} tree1, tree2;
void DFS(int u) {
long long sum = 0;
for (int v : ke[u]) {
DFS(v);
sum += dp[v];
}
tree1.update(tin[u], tout[u], sum);
dp[u] = sum;
for (auto x : stars[u]) {
dp[u] = max(dp[u], x.second + tree1.get(tin[x.first]) - tree2.get(tin[x.first]) + dp[x.first]);
}
tree2.update(tin[u], tout[u], dp[u]);
}
__Dennis_Tran___{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n;
FOR(i, 1, n) cin >> a[i];
a[n + 1] = n; ++n;
RMQ.build();
int root = build_Tree(1, n);
long long Total = 0;
int m; cin >> m; while (m--) {
int x, y, c; cin >> x >> y >> c;
int cnode = x; Total += c;
FOD(i, 18, 0) if (p[i][cnode] && a[p[i][cnode]] < y)
cnode = p[i][cnode];
cnode = p[0][cnode];
stars[cnode].emplace_back(x, c);
}
DFS(root);
cout << Total - dp[root];
cerr << "Time elapsed: " << TIME << " s.\n";
return (0 ^ 0);
}
Compilation message
constellation3.cpp: In member function 'void rmq::build()':
constellation3.cpp:32:65: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
32 | f[i][j] = Max(f[i - 1][j], f[i - 1][j + (1 << i - 1)]);
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
10076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
10076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
10076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
