#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define MAX 301010
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
struct Star {
ll x, y, c, ban;
Star() :x(0), y(0), c(0), ban(0) {}
Star(ll x, ll y, ll c) :x(x), y(y), c(c), ban(0) {}
};
struct segtree {
vector<ll> l, r, tree;
ll s;
ll type;
void init(ll x = 1) {
if (x >= s) {
l[x] = r[x] = x - s + 1;
return;
}
init(x * 2);
init(x * 2 + 1);
l[x] = l[x * 2];
r[x] = r[x * 2 + 1];
if (type == 1) tree[x] = tree[x * 2] + tree[x * 2 + 1];
else tree[x] = max(tree[x * 2], tree[x * 2 + 1]);
}
void update(ll x, ll a) {
x += s - 1;
tree[x] = a;
x /= 2;
while (x) {
if (type == 1) tree[x] = tree[x * 2] + tree[x * 2 + 1];
else tree[x] = max(tree[x * 2], tree[x * 2 + 1]);
x /= 2;
}
}
ll query(ll low, ll high, ll loc = 1) {
if (l[loc] == low && r[loc] == high) return tree[loc];
if (high <= r[loc * 2]) return query(low, high, loc * 2);
if (low >= l[loc * 2 + 1]) return query(low, high, loc * 2 + 1);
if (type == 1) return query(low, r[loc * 2], loc * 2) + query(l[loc * 2 + 1], high, loc * 2 + 1);
else return max(query(low, r[loc * 2], loc * 2), query(l[loc * 2 + 1], high, loc * 2 + 1));
}
segtree(ll N) {
type = 1;
s = 1LL << (ll)ceil(log2(N));
tree.resize(2 * s + 1);
l.resize(2 * s + 1);
r.resize(2 * s + 1);
}
segtree() {
}
};
ll A[MAX];
ll lc[MAX], rc[MAX];
ll sp[MAX][MAXS];
ll bottom[MAX], revb[MAX];
ll sz[MAX];
ll sum[MAX];
ll ans[MAX];
ll depth[MAX];
Star star[MAX];
vector<ll> cart[MAX];
vector<vector<ll>> chain;
pll cnum[MAX];
vector<segtree> chainseg;
ll S, N, M;
ll cnt;
segtree aseg;
ll make_tree(ll l, ll r, ll num, ll p, ll d) {
sz[num] = r - l + 1;
ll res = aseg.query(l, r);
ll mid = res % 1000000;
bottom[mid] = num;
depth[num] = d;
revb[num] = mid;
sp[num][0] = p;
for (ll i = 1; i < MAXS; i++) sp[num][i] = sp[sp[num][i - 1]][i - 1];
if (l <= mid - 1) lc[num] = make_tree(l, mid - 1, ++S, num, d + 1);
else lc[num] = 0;
if (mid + 1 <= r) rc[num] = make_tree(mid + 1, r, ++S, num, d + 1);
else rc[num] = 0;
return num;
}
void assign_star() {
ll i, j;
for (i = 1; i <= M; i++) {
ll v = bottom[star[i].x];
star[i].ban = v;
for (j = MAXS; j > 0; j--) {
if (A[revb[sp[v][j]]] < star[i].y) v = sp[v][j];
}
cart[v].push_back(i);
}
}
void make_chain(ll x, ll p = 0) {
chain[cnt].push_back(x);
cnum[x] = { cnt, chain[cnt].size() - 1 };
ll a, b;
a = lc[x], b = rc[x];
if (sz[lc[x]] < sz[rc[x]]) swap(a, b);
if (a) make_chain(a, x);
if (b) {
cnt++;
chain.push_back(vector<ll>());
make_chain(b, x);
}
}
void make_seg() {
for (ll i = 0; i < chain.size(); i++) chainseg.push_back(segtree(chain[i].size()));
for (ll i = 0; i < chain.size(); i++) chainseg[i].init();
}
ll lca(ll u, ll v) {
if (!(u * v)) return -1;
if (u == v) return u;
ll i;
if (depth[u] != depth[v]) {
if (depth[u] > depth[v]) swap(u, v);
for (i = MAXS - 1; i >= 0; i--) if (depth[sp[v][i]] >= depth[u]) v = sp[v][i];
}
if (u == v) return u;
for (i = MAXS - 1; i >= 0; i--) if (sp[u][i] != sp[v][i]) u = sp[u][i], v = sp[v][i];
return sp[u][0];
}
void update(ll x, ll a) {
if (!x) return;
chainseg[cnum[x].first].update(cnum[x].second + 1, a);
}
ll f(ll x) {
ll s;
if (lc[sp[x][0]] == x) s = rc[sp[x][0]];
else s = lc[sp[x][0]];
return s;
}
ll query(ll u, ll v) {
ll ret = 0;
ll l = lca(u, v);
while (cnum[u].first != cnum[l].first) ret += chainseg[cnum[u].first].query(1, cnum[u].second + 1), u = sp[chain[cnum[u].first][0]][0];
while (cnum[v].first != cnum[l].first) ret += chainseg[cnum[v].first].query(1, cnum[v].second + 1), v = sp[chain[cnum[v].first][0]][0];
ret += chainseg[cnum[l].first].query(cnum[l].second + 1, cnum[u].second + 1);
ret += chainseg[cnum[l].first].query(cnum[l].second + 1, cnum[v].second + 1);
ret -= chainseg[cnum[l].first].query(cnum[l].second + 1, cnum[l].second + 1);
return ret;
}
void calc(ll x = 1, ll p = 0) {
if (!x) return;
calc(lc[x]);
calc(rc[x]);
sum[x] = ans[lc[x]] + ans[rc[x]];
ans[x] = sum[x];
for (auto asdf : cart[x]) {
Star st = star[asdf];
ll b = st.ban;
if (b == x) ans[x] = max(sum[x] + st.c, ans[x]);
else {
ll s;
if (lca(b, lc[x]) == lc[x]) s = lc[x];
else s = rc[x];
ans[x] = max(sum[b] + query(b, s) + st.c, ans[x]);
}
}
if (x != 1) update(f(x), ans[x]);
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
cin >> N;
A[0] = INF;
ll i;
aseg = segtree(N);
aseg.type = 0;
for (i = 1; i <= N; i++) cin >> A[i], aseg.tree[i + aseg.s - 1] = 1000000 * A[i] + i;
aseg.init();
cin >> M;
ll asdfsdf = 0;
for (i = 1; i <= M; i++) cin >> star[i].x >> star[i].y >> star[i].c, asdfsdf += star[i].c;
S = 1;
make_tree(1, N, 1, 0, 1);
assign_star();
chain.push_back(vector<ll>());
make_chain(1);
make_seg();
calc();
cout << asdfsdf - ans[1] << ln;
}
Compilation message
constellation3.cpp: In function 'void make_seg()':
constellation3.cpp:119:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
119 | for (ll i = 0; i < chain.size(); i++) chainseg.push_back(segtree(chain[i].size()));
| ~~^~~~~~~~~~~~~~
constellation3.cpp:120:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
120 | for (ll i = 0; i < chain.size(); i++) chainseg[i].init();
| ~~^~~~~~~~~~~~~~
constellation3.cpp: In function 'll lca(ll, ll)':
constellation3.cpp:123:10: warning: '*' in boolean context, suggest '&&' instead [-Wint-in-bool-context]
123 | if (!(u * v)) return -1;
| ~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
16972 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
16972 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
16972 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
