#include <bits/stdc++.h>
using namespace std;
#ifdef MIKU
#define debug(x...) cout << '[' << #x << "] : ", dout(x)
void dout() { cout << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif
// #define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for(int i = j, Z = k; i < k; i++)
typedef long long ll;
typedef pair<int, int> pii;
const int MXN = 200005;
int n, m, a[MXN], px[MXN], py[MXN], pc[MXN];
vector<int> v[MXN];
struct SMG {
int val[MXN * 4];
void build(int id, int l, int r) {
if (l + 1 == r) {
val[id] = l;
return;
}
int mid = (l + r) >> 1;
build(id * 2 + 1, l, mid);
build(id * 2 + 2, mid, r);
val[id] = (a[val[id * 2 + 1]] >= a[val[id * 2 + 2]] ? val[id * 2 + 1] : val[id * 2 + 2]);
}
int query(int id, int l, int r, int _l, int _r) {
if (_r <= l || r <= _l) return 0;
if (_l <= l && r <= _r) return val[id];
int mid = (l + r) >> 1;
int vl = query(id * 2 + 1, l, mid, _l, _r), vr = query(id * 2 + 2, mid, r, _l, _r);
return (a[vl] >= a[vr] ? vl : vr);
}
void DFS(int id, int l, int r) {
debug(l, r, val[id]);
if (l + 1 == r) return;
int mid = (l + r) >> 1;
DFS(id * 2 + 1, l, mid);
DFS(id * 2 + 2, mid, r);
}
} smg;
struct BIT {
int n, val[MXN];
void init(int _n) {
n = _n;
fill(val + 1, val + n + 1, 0);
}
void modify(int id, int v) {
for (; id <= n; id += (id & -id)) val[id] += v;
}
int query(int id) {
int ans = 0;
for (; id > 0; id -= (id & -id)) ans += val[id];
return ans;
}
} B;
namespace CT {
int rt, flc = 1;
pii ct[MXN], fl[MXN];
// int pos[MXN];
int build(int l, int r) {
if (l >= r) return -1;
int rt = smg.query(0, 0, n + 1, l, r);
ct[rt].fs = build(l, rt);
ct[rt].sc = build(rt + 1, r);
return rt;
}
void FLAT(int id) {
fl[id].fs = flc++;
if (ct[id].fs != -1) FLAT(ct[id].fs);
if (ct[id].sc != -1) FLAT(ct[id].sc);
fl[id].sc = flc;
}
void DFS(int id, ll &x) {
if (ct[id].fs != -1) DFS(ct[id].fs, x);
if (ct[id].sc != -1) DFS(ct[id].sc, x);
int ans = 0;
for (auto &i : v[id]) {
// debug(pc[i], px[i], B.query(fl[px[i]].fs));
int now = pc[i];
now -= B.query(fl[px[i]].fs);
ans = max(ans, now);
}
debug(id, ans);
// debug(fl[id].fs, fl[id].sc);
x -= ans;
B.modify(fl[id].fs, ans);
B.modify(fl[id].sc, -ans);
// FOR(i, 1, n + 1) cout << B.val[i] << ' ';
// cout << endl;
}
}
namespace PUT {
set<int> S;
vector<pii> op;
void DO() {
S.insert(0);
S.insert(n + 1);
FOR(i, 1, n + 1) op.push_back(mp(a[i], i));
FOR(i, 1, m + 1) op.push_back(mp(py[i], -i));
sort(op.begin(), op.end(), greater<pii>());
for (auto &i : op) {
int id = abs(i.sc);
if (i.sc > 0) S.insert(id);
else {
auto itr = S.upper_bound(px[id]);
auto itl = prev(itr);
v[smg.query(0, 0, n + 1, *itl + 1, *itr)].push_back(id);
}
}
}
}
void miku() {
cin >> n;
FOR(i, 1, n + 1) cin >> a[i];
cin >> m;
FOR(i, 1, m + 1) cin >> px[i] >> py[i] >> pc[i];
smg.build(0, 0, n + 1);
CT::rt = smg.query(0, 0, n + 1, 1, n + 1);
CT::build(1, n + 1);
CT::FLAT(CT::rt);
// FOR(i, 1, n + 1) debug(CT::fl[i].fs, CT::fl[i].sc);
PUT::DO();
// return;
B.init(n);
ll ans = 0;
CT::DFS(CT::rt, ans);
FOR(i, 1, m + 1) ans += pc[i];
// FOR(i, 1, n + 1) ans -= B.query(i);
cout << ans << '\n';
}
int32_t main() {
cin.tie(0) -> sync_with_stdio(false);
miku();
return 0;
}
Compilation message
constellation3.cpp: In member function 'void SMG::DFS(int, int, int)':
constellation3.cpp:10:20: warning: statement has no effect [-Wunused-value]
10 | #define debug(...) 39
| ^~
constellation3.cpp:45:9: note: in expansion of macro 'debug'
45 | debug(l, r, val[id]);
| ^~~~~
constellation3.cpp: In function 'void CT::DFS(int, ll&)':
constellation3.cpp:10:20: warning: statement has no effect [-Wunused-value]
10 | #define debug(...) 39
| ^~
constellation3.cpp:99:9: note: in expansion of macro 'debug'
99 | debug(id, ans);
| ^~~~~
constellation3.cpp: In function 'void PUT::DO()':
constellation3.cpp:17:37: warning: unused variable 'Z' [-Wunused-variable]
17 | #define FOR(i, j, k) for(int i = j, Z = k; i < k; i++)
| ^
constellation3.cpp:116:9: note: in expansion of macro 'FOR'
116 | FOR(i, 1, n + 1) op.push_back(mp(a[i], i));
| ^~~
constellation3.cpp:17:37: warning: unused variable 'Z' [-Wunused-variable]
17 | #define FOR(i, j, k) for(int i = j, Z = k; i < k; i++)
| ^
constellation3.cpp:117:9: note: in expansion of macro 'FOR'
117 | FOR(i, 1, m + 1) op.push_back(mp(py[i], -i));
| ^~~
constellation3.cpp: In function 'void miku()':
constellation3.cpp:17:37: warning: unused variable 'Z' [-Wunused-variable]
17 | #define FOR(i, j, k) for(int i = j, Z = k; i < k; i++)
| ^
constellation3.cpp:133:5: note: in expansion of macro 'FOR'
133 | FOR(i, 1, n + 1) cin >> a[i];
| ^~~
constellation3.cpp:17:37: warning: unused variable 'Z' [-Wunused-variable]
17 | #define FOR(i, j, k) for(int i = j, Z = k; i < k; i++)
| ^
constellation3.cpp:135:5: note: in expansion of macro 'FOR'
135 | FOR(i, 1, m + 1) cin >> px[i] >> py[i] >> pc[i];
| ^~~
constellation3.cpp:17:37: warning: unused variable 'Z' [-Wunused-variable]
17 | #define FOR(i, j, k) for(int i = j, Z = k; i < k; i++)
| ^
constellation3.cpp:146:5: note: in expansion of macro 'FOR'
146 | FOR(i, 1, m + 1) ans += pc[i];
| ^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 2 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
12768 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 2 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
12768 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 2 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
12768 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
