#include<bits/stdc++.h>
using namespace std;
typedef long long llint;
typedef pair <int, int> pi;
const int MAXN = 200005;
int n, m, ofs = 1, sum;
int h[MAXN], x[MAXN], y[MAXN], cost[MAXN], val[MAXN];
llint mx[MAXN * 4], star[MAXN * 4], t[MAXN * 4], prop[MAXN * 4];
vector <int> v[MAXN];
inline int spoji_mx (int a, int b) {return h[a] >= h[b] ? a : b;}
inline int spoji_star (int a, int b) {return val[a] >= val[b] ? a : b;}
void tour_init () {
for (int i = 0; i < 2*ofs; i++) {
mx[i] = star[i] = n;
}
for (int i = 0; i < n; i++) {
mx[i + ofs] = star[i + ofs] = i;
if (v[i].empty()) val[i] = 0; else val[i] = y[v[i].back()];
}
for (int i = ofs-1; i > 0; i--) {
mx[i] = spoji_mx(mx[i * 2], mx[i * 2 + 1]);
star[i] = spoji_star(star[i * 2], star[i * 2 + 1]);
}
}
void propagate (int x) {
if (prop[x] == 0) return;
if (x < ofs) {
prop[2 * x] += prop[x];
prop[2 * x + 1] += prop[x];
} else {
t[x] += prop[x];
}
prop[x] = 0;
}
int upit_mx (int x, int from, int to, int lo, int hi) {
if (from <= lo && hi <= to) return mx[x];
if (to < lo || hi < from) return n;
return spoji_mx(upit_mx(2 * x, from, to, lo, (lo + hi) / 2), upit_mx(2 * x + 1, from, to, (lo + hi) / 2 + 1, hi));
}
int upit_star (int x, int from, int to, int lo, int hi) {
if (from <= lo && hi <= to) return star[x];
if (to < lo || hi < from) return n;
return spoji_star(upit_star(2 * x, from, to, lo, (lo + hi) / 2), upit_star(2 * x + 1, from, to, (lo + hi) / 2 + 1, hi));
}
int upit_t (int x, int pos, int lo, int hi) {
propagate(x);
if (lo == hi) return t[x];
if (pos <= (lo + hi) / 2) return upit_t(2 * x, pos, lo, (lo + hi) / 2);
return upit_t(2 * x + 1, pos, (lo + hi) / 2 + 1, hi);
}
void update_star (int pos) {
v[pos].pop_back();
if (v[pos].empty()) val[pos] = 0; else val[pos] = y[v[pos].back()];
pos = (pos + ofs) / 2;
while (pos > 0) {
star[pos] = spoji_star(star[pos * 2], star[pos * 2 + 1]);
pos /= 2;
}
}
void update_t (int x, int from, int to, int lo, int hi, int d) {
propagate(x);
if (from <= lo && hi <= to) {
prop[x] += d;
propagate(x);
return;
}
if (to < lo || hi < from) return;
update_t(2 * x, from, to, lo, (lo + hi) / 2, d);
update_t(2 * x + 1, from, to, (lo + hi) / 2 + 1, hi, d);
}
bool cmp (int a, int b) {
return y[a] < y[b];
}
llint solve (int a, int b) {
if (a > b) return 0;
//cout << "sad na " << a << " " << b << endl;
int mid = upit_mx(1, a, b, 0, ofs - 1);
vector <int> p;
while (1) {
int pos = upit_star(1, a, b, 0, ofs - 1);
if (val[pos] <= h[mid]) break;
p.push_back(v[pos].back());
update_star(pos);
}
llint lef = solve(a, mid - 1);
llint rig = solve(mid + 1, b);
llint res = lef + rig;
if (a < mid) update_t(1, a, mid - 1, 0, ofs - 1, rig);
if (mid < b) update_t(1, mid + 1, b, 0, ofs - 1, lef);
update_t(1, mid, mid, 0, ofs - 1, lef + rig);
for (auto ind : p) {
llint tmp = upit_t(1, x[ind], 0, ofs - 1) + cost[ind];
res = max(res, tmp);
}
return res;
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n;
while (ofs < n) ofs *= 2;
for (int i = 0; i < n; i++) {
cin >> h[i];
}
cin >> m;
for (int i = 0; i < m; i++) {
cin >> x[i] >> y[i] >> cost[i];
x[i]--;
v[x[i]].push_back(i);
sum += cost[i];
}
for (int i = 0; i < n; i++) {
sort(v[i].begin(), v[i].end(), cmp);
}
tour_init();
cout << sum - solve(0, n - 1);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
5120 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
5120 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
5120 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
5120 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
5120 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
5120 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
