#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
using namespace std;
using ll = long long;
const int MAXN = (int)(2e5) + 5;
struct Seg {
ll mx[4*MAXN];
Seg() {
memset(mx, 0, sizeof(mx));
}
void upd(int i, ll val, int n = 1, int tl = 0, int tr = MAXN-1) {
if (tl == tr) {
if (val == -1) {
mx[n] = -1;
}
else {
mx[n] = max(mx[n], val);
}
}
else {
int tm = (tl + tr)/2;
if (i <= tm) {
upd(i, val, 2*n, tl, tm);
}
else {
upd(i, val, 2*n+1, tm+1, tr);
}
mx[n] = max(mx[2*n], mx[2*n+1]);
}
}
ll get(int l, int r, int n = 1, int tl=0,int tr=MAXN-1) {
if (l <= tl && tr <= r) {
return mx[n];
}
else if (r < tl || l > tr) {
return -1;
}
else {
int tm = (tl + tr)/2;
return max(get(l, r, 2*n, tl, tm), get(l, r, 2*n+1, tm+1, tr));
}
}
};
Seg byY;
Seg byX;
Seg heights;
int A[MAXN];
vector<pair<int, ll>> store[MAXN];
int main() {
cin.tie(0);
cin.sync_with_stdio(0);
int N;
cin >> N;
FR(i, N) cin >> A[i];
int M;
cin >> M;
ll tot = 0;
FR(i, M) {
int a, b, c;
cin >> a >> b >> c;
tot += c;
a--;
store[a].push_back({b, c});
}
FR(i, MAXN) {
heights.upd(i, -1);
}
ll curMax = 0;
FR(i, N) {
curMax = max(curMax, byY.get(0, A[i]));
for (auto point : store[i]) {
// cout << heights.get(point.first, N) << endl;
ll next = max(curMax, byX.get(0, heights.get(point.first, MAXN-1))) + point.second;
byX.upd(i, next);
byY.upd(point.first, curMax+point.second);
}
heights.upd(A[i], i);
}
cout << tot - byX.get(0, MAXN-1) << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
23788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
23788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
23788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
