#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
template <class T, class... U> void bug_h(const T& t, const U&... u) { cerr << t; ((cerr << " | " << u), ...); cerr << endl; }
#define bug(...) cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: ", bug_h(__VA_ARGS__)
#else
#define cerr if (0) cerr
#define bug(...)
#endif
#define ar array
#define all(v) std::begin(v), std::end(v)
#define sz(v) int(std::size(v))
typedef long long i64;
typedef vector<int> vi;
typedef pair<int, int> pi;
int N;
vi A;
struct segt {
int l, r; pi mx;
segt *lc, *rc;
segt(int l, int r) : l(l), r(r) {
if (l == r) mx = pi(A[l], l);
else {
int m = (l + r) / 2;
lc = new segt(l, m), rc = new segt(m + 1, r);
mx = max(lc->mx, rc->mx);
}
}
pi qry(int ql, int qr) {
if (ql <= l && qr >= r) return mx;
if (qr <= lc->r) return lc->qry(ql, qr);
if (ql >= rc->l) return rc->qry(ql, qr);
return max(lc->qry(ql, qr), rc->qry(ql, qr));
}
} *tmax;
struct node {
vector<node *> kids;
vector<pi> items;
node *jump[18];
int l, r, low, hi;
};
vector<node *> who;
node *rec(node *parent, int l, int r, int upper) {
node *v = new node();
if (parent == NULL) parent = v;
v->jump[0] = parent;
for (int l = 1; l < 18; l++)
v->jump[l] = v->jump[l - 1]->jump[l - 1];
v->l = l;
v->r = r;
v->hi = upper;
int target = tmax->qry(l, r).first;
v->low = target + 1;
vector<int> cuts; int p = l;
while (p <= r) {
auto x = tmax->qry(p, r);
if (x.first == target) {
cuts.push_back(x.second);
p = x.second + 1;
} else break;
}
for (int j : cuts) who[j] = v;
if (l < cuts.at(0)) v->kids.push_back(rec(v, l, cuts[0] - 1, target));
for (int i = 0; i < sz(cuts) - 1; i++) if (cuts[i] + 1 < cuts[i + 1])
v->kids.push_back(rec(v, cuts[i] + 1, cuts[i + 1] - 1, target));
if (cuts.at(sz(cuts) - 1) < r) v->kids.push_back(rec(v, cuts.back() + 1, r, target));
return v;
}
i64 calc(node *v) {
vector<i64> y(sz(v->kids));
i64 tot = 0;
for (int i = 0; i < sz(v->kids); i++) {
y[i] = calc(v->kids[i]);
tot += y[i];
}
i64 add = 0;
for (auto [i, w] : v->items) {
int low = 0, hi = sz(v->kids) - 1;
while (low < hi) {
int mid = (low + hi) / 2;
if (i >= v->kids[mid]->l) hi = mid;
else low = mid + 1;
}
int j = low;
i64 x = w;
if (0 <= j && j < sz(v->kids) && v->kids[j]->r >= i)
x -= y[j];
add = max(add, x);
}
return tot + add;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N;
A.resize(N);
for (auto& x : A) cin >> x;
tmax = new segt(0, N - 1);
who.resize(N, NULL);
node *root = rec(NULL, 0, N - 1, N);
int K;
cin >> K;
i64 sum = 0;
while (K--) {
int i, j, w;
cin >> i >> j >> w, i--;
sum += w;
node *v = who[i];
for (int l = 17; l >= 0; l--) {
assert(v != NULL);
if (v->jump[l]->low <= j)
v = v->jump[l];
}
assert(v != NULL);
assert(v->low <= j && j <= v->hi);
v->items.push_back({i, w});
}
cout << sum - calc(root) << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
