#include<iostream>
#include<deque>
#include<algorithm>
#include<vector>
#include<map>
#include<random>
#include<time.h>
#include<cassert>
#include<chrono>
#include<set>
#include<unordered_set>
#include<array>
using namespace std;
#define ull unsigned long long
#define pb push_back
#define ll long long
#define all(a) a.begin(), a.end()
#define ld long double
#define int long long
mt19937_64 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
struct SegTree {
vector<pair<int, int>> t;
int n;
SegTree(int n_) {
n = 1;
while (n < n_) {
n *= 2;
}
t.resize(2 * n);
}
void upd(int i, pair<int, int> val) {
i += n;
t[i] = val;
for (; i > 1; i /= 2) {
t[i / 2] = max(t[i], t[i ^ 1]);
}
}
pair<int, int> get(int l, int r) {
l += n, r += n + 1;
pair<int, int> ans{-1, -1};
while (l < r) {
if (l & 1) {
ans = max(ans, t[l++]);
}
if (r & 1) {
ans = max(ans, t[--r]);
}
l /= 2, r /= 2;
}
return ans;
}
};
const ll super_inf = 1e18;
const int N = 2e5 + 10;
vector<pair<int, ll>> mas[N];
int a[N];
SegTree tr(N);
ll t[4 * N], add[4 * N];
void inc(int v, ll val) {
t[v] += val;
add[v] += val;
}
void push(int v) {
inc(v * 2, add[v]);
inc(v * 2 + 1, add[v]);
add[v] = 0;
}
void update_pos(int v, int l, int r, int pos, ll val) {
if (l == r) {
if (val == -super_inf) {
t[v] = val;
} else {
t[v] = max(t[v], val);
}
return;
}
push(v);
int m = (l + r) / 2;
if (pos <= m) {
update_pos(2 * v, l, m, pos, val);
} else {
update_pos(2 * v + 1, m + 1, r, pos, val);
}
t[v] = max(t[v * 2], t[v * 2 + 1]);
}
void update(int v, int tl, int tr, int l, int r, ll val) {
if (l > r) return;
if (tl == l && tr == r) {
inc(v, val);
return;
}
push(v);
int tm = (tl + tr) / 2;
update(2 * v, tl, tm, l, min(r, tm), val);
update(2 * v + 1, tm + 1, tr, max(l, tm + 1), r, val);
t[v] = max(t[v * 2], t[v * 2 + 1]);
}
ll get(int v, int tl, int tr, int l, int r) {
if (l > r) return -super_inf;
if (tl == l && tr == r) {
return t[v];
}
push(v);
int tm = (tl + tr) / 2;
return max(get(2 * v, tl, tm, l, min(r, tm)), get(2 * v + 1, tm + 1, tr, max(l, tm + 1), r));
}
int pr[N];
set<int> sets[N];
int solve(int l, int r) {
if (l > r) return N - 1;
if (l == r) {
for (auto p : mas[l]) {
sets[l].insert(p.first);
update_pos(1, 0, N - 1, p.first, p.second);
}
return l;
}
int m = tr.get(l, r).second;
int sz1 = pr[m] - pr[l], sz2 = pr[r + 1] - pr[m + 1], i, j;
vector<array<ll, 3>> lol;
if (sz1 > sz2) {
j = solve(m + 1, r);
for (int p : sets[j]) {
lol.pb({p, get(1, 0, N - 1, p, p), 0});
update_pos(1, 0, N - 1, p, -super_inf);
}
assert(t[1] < 0);
i = solve(l, m - 1);
} else {
j = solve(l, m - 1);
for (int p : sets[j]) {
lol.pb({p, get(1, 0, N - 1, p, p), 0});
update_pos(1, 0, N - 1, p, -super_inf);
}
assert(t[1] < 0);
i = solve(m + 1, r);
}
for (int p : sets[j]) {
sets[i].insert(p);
}
for (int i = 0; i < lol.size(); i++) {
if (lol[i][0] <= a[m]) {
lol[i][2] = max(0ll, get(1, 0, N - 1, 0, lol[i][0]));
}
}
ll best2 = max(0ll, get(1, 0, N - 1, 0, a[m]));
ll cur_mx = 0, best1 = 0;
int last = -1;
for (int i = 0; i < lol.size(); i++) {
int R = min(a[m], (i + 1 < lol.size() ? lol[i + 1][0] - 1 : N - 1));
cur_mx = max(cur_mx, lol[i][1]);
if (lol[i][0] <= a[m]) {
best1 = max(best1, lol[i][1]);
}
assert(last < lol[i][0]);
update(1, 0, N - 1, lol[i][0], R, cur_mx);
last = R;
}
assert(last < a[m] + 1);
update(1, 0, N - 1, a[m] + 1, N - 1, best1);
for (int i = 0; i < lol.size(); i++) {
if (lol[i][0] <= a[m]) {
update_pos(1, 0, N - 1, lol[i][0], lol[i][2] + lol[i][1]);
} else {
update_pos(1, 0, N - 1, lol[i][0], best2 + lol[i][1]);
}
}
for (auto p : mas[m]) {
update_pos(1, 0, N - 1, p.first, p.second + best1 + best2);
sets[i].insert(p.first);
}
return i;
}
signed main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif // LOCAL
ios_base::sync_with_stdio(0);
cin.tie(0);
for (int i = 0; i < 4 * N; i++) {
t[i] = -super_inf;
}
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < n; i++) {
tr.upd(i, {a[i], i});
}
int m;
cin >> m;
ll sum = 0;
for (int i = 0; i < m; i++) {
int x, y, c;
cin >> x >> y >> c;
x--;
if (y <= a[x]) continue;
sum += c;
mas[x].pb({y, c});
}
for (int i = 0; i < n; i++) {
pr[i + 1] = pr[i] + mas[i].size();
}
solve(0, n - 1);
ll mx = get(1, 0, N - 1, 0, N - 1);
cout << sum - mx << endl;
return 0;
}
Compilation message
constellation3.cpp: In function 'long long int solve(long long int, long long int)':
constellation3.cpp:154:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
154 | for (int i = 0; i < lol.size(); i++) {
| ~~^~~~~~~~~~~~
constellation3.cpp:162:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
162 | for (int i = 0; i < lol.size(); i++) {
| ~~^~~~~~~~~~~~
constellation3.cpp:163:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
163 | int R = min(a[m], (i + 1 < lol.size() ? lol[i + 1][0] - 1 : N - 1));
| ~~~~~~^~~~~~~~~~~~
constellation3.cpp:174:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
174 | for (int i = 0; i < lol.size(); i++) {
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
34396 KB |
Output is correct |
| 2 |
Correct |
9 ms |
34392 KB |
Output is correct |
| 3 |
Incorrect |
13 ms |
34396 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
34396 KB |
Output is correct |
| 2 |
Correct |
9 ms |
34392 KB |
Output is correct |
| 3 |
Incorrect |
13 ms |
34396 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
34396 KB |
Output is correct |
| 2 |
Correct |
9 ms |
34392 KB |
Output is correct |
| 3 |
Incorrect |
13 ms |
34396 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
