#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(V) V.begin(),V.end()
vector<int> G[400010], S[400010];
pair<int, int> P[400010], st[400010];
int W[400010], A[200010], seg[524288], rt[524288], as[1048576], lc[1048576];
vector<pair<int, int>> H;
vector<int> T[400010];
tuple<int, int, int> R[400010];
int par[400010];
set<int> soko;
ll arr[400010];
queue<int> Q;
int hlnum[400010], hlseg[400010], hltop[400010], hlpar[400010];
//hlnumはhl分解後の「セグ木上での番号」、hlsegはhl分解後のセグ木のx番目の「頂点番号」、hltopはその頂点が属する鎖の一番根に近いやつの「頂点番号」、hlparは鎖の繋がっている親ノードの「頂点番号」
int wgh(int x) {
if (T[x].size() == 0) {
W[x] = 1;
return 1;
}
int a = 1;
for (int j : T[x])a += wgh(j);
W[x] = a;
return a;
}
void hld(int x, int me, int& num) {
int mw = 0, ms = 0;
hlnum[x] = num;
hlseg[num] = x;
hltop[x] = me;
if (T[x].size() == 0)return;
for (int i : T[x]) {
if (W[i] > mw)ms = i, mw = W[i];
}
num++;
hld(ms, me, num);
for (int i : T[x]) {
if (i != ms) {
hlpar[i] = x;
num++;
hld(i, i, num);
}
}
}
void raq_as(int s, int t, ll v, int k = 1, int l = 0, int r = 524287) {
if (t < l || r < s)return;
if (s <= l && r <= t) {
as[k] += v;
return;
}
raq_as(s, t, v, k * 2, l, (l + r) / 2);
raq_as(s, t, v, k * 2 + 1, (l + r) / 2 + 1, r);
}
ll rsq_lc(int s, int t, int k = 1, int l = 0, int r = 524287) {
if (t < l || r < s)return 0;
if (s <= l && r <= t) {
return lc[k];
}
ll lv = rsq_lc(s, t, k * 2, l, (l + r) / 2);
ll rv = rsq_lc(s, t, k * 2 + 1, (l + r) / 2 + 1, r);
return lv + rv;
}
void add_lc(int x, ll v) {
x += 524288;
while (x) {
lc[x] += v;
x /= 2;
}
return;
}
ll get_as(int x) {
x += 524288;
ll ans = 0;
while (x) {
ans += as[x];
x /= 2;
}
return ans;
}
void solve2(int x, ll dif) {
int tp = hlnum[x];
int tpp = hlnum[hltop[x]];
add_lc(tp, dif);//lcへの加算
raq_as(tpp, tp, dif);//asの加算
if (hlpar[hltop[x]] == 0)return;
solve2(hlpar[hltop[x]], dif);
}
void solve(int x, int y, ll val, bool fir = 0) {
int tp = hlnum[x];//セグ木上での番号
int tpp = hlnum[hltop[x]];//鎖のtopのセグ木上での番号
if (fir) {
val += rsq_lc(tp, tp);
}
if (get<2>(R[hltop[x]]) < y) {
val += rsq_lc(tpp, tp - 1);//lcの和
if (T[x].size()) {
val += get_as(tp + 1);//asの点取得
}
solve(hlpar[hltop[x]], y, val);
}
else {
int ok = tpp, ng = tp + 1, mid;
while (ok + 1 != ng) {
mid = (ok + ng) / 2;
if (get<2>(R[hlseg[mid]]) < y) {
ng = mid;
}
else {
ok = mid;
}
}
val += rsq_lc(ok, tp - 1);//lcの和
if (T[x].size())
val += get_as(tp + 1);
ll alr = get_as(ok);
if (alr < val) {
raq_as(tpp, ok, val - alr);//asの加算
solve2(hlpar[hltop[x]], val - alr);
}
}
}
int rmq(int s, int t, int k = 1, int l = 0, int r = 262143) {
if (t < l || r < s)return INT32_MIN;
if (s <= l && r <= t) {
return seg[k];
}
int lv = rmq(s, t, k * 2, l, (l + r) / 2);
int rv = rmq(s, t, k * 2 + 1, (l + r) / 2 + 1, r);
return max(lv, rv);
}
void ruq(int s, int t, int v, int k = 1, int l = 0, int r = 262143) {
if (t < l || r < s)return;
if (s <= l && r <= t) {
rt[k] = v;
return;
}
if (rt[k]) {
rt[k * 2] = rt[k];
rt[k * 2 + 1] = rt[k];
rt[k] = 0;
}
ruq(s, t, v, k * 2, l, (l + r) / 2);
ruq(s, t, v, k * 2 + 1, (l + r) / 2 + 1, r);
}
int gets(int x) {
x += 262144;
int ans = 0;
while (x) {
if (rt[x])ans = rt[x];
x /= 2;
}
return ans;
}
void say(tuple<int, int, int>X) {
int a, b, c;
tie(a, b, c) = X;
cout << a << " " << b << " " << c << endl;
}
void make_skytree(int l, int r, int& num) {
int m = rmq(l, r), me = num;
pair<int, int> ser = { m,l };
auto it = lower_bound(all(H), ser);
ser = { m,r + 1 };
auto it2 = lower_bound(all(H), ser);
int li = l, t;
for (auto i = it;;i++) {
if (i == it2)
t = r;
else {
t = (*i).second - 1;
ruq(t + 1, t + 1, me);
}
if (li <= t) {
num++;
ruq(li, t, num);
T[me].push_back(num);
R[num] = make_tuple(li, t, m);
par[num] = me;
make_skytree(li, t, num);
}
li = t + 2;
if (i == it2)break;
}
if (T[me].size() == 0) {
Q.push(me);
}
}
int main() {
for (int i = 0;i < 524288;i++)seg[i] = 0;
int N, M;
cin >> N;
R[1] = make_tuple(1, N, N + 3);
for (int i = 0;i < N;i++) {
cin >> A[i];
seg[i + 262145] = A[i];
H.push_back({ A[i],i + 1 });
}
sort(all(H));
for (int i = 262143;i >= 0;i--) {
seg[i] = max(seg[i * 2], seg[i * 2 + 1]);
}
par[1] = 0;
int a = 1;
make_skytree(1, N, a);
wgh(1);
st[1] = { 1,0 };
P[1] = { 0,0 };
a = 1;
hld(1, 1, a);
cin >> M;
ll X, Y, C, xi, alc = 0;
vector<tuple<ll, ll, ll>> V(M);
for (int i = 0;i < M;i++) {
cin >> X >> Y >> C;
xi = gets(X);
alc += C;
V[i] = make_tuple(Y, xi, C);
}
sort(all(V));
int bef = 0;
ll ans;
for (int i = 0;i < M;i++) {
tie(Y, xi, C) = V[i];
solve(xi, Y, C, 1);
}
cout << alc - get_as(1) << endl;
}
Compilation message
constellation3.cpp: In function 'int main()':
constellation3.cpp:248:6: warning: unused variable 'bef' [-Wunused-variable]
int bef = 0;
^~~
constellation3.cpp:249:5: warning: unused variable 'ans' [-Wunused-variable]
ll ans;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
30720 KB |
Output is correct |
| 2 |
Incorrect |
22 ms |
30848 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
30720 KB |
Output is correct |
| 2 |
Incorrect |
22 ms |
30848 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
30720 KB |
Output is correct |
| 2 |
Incorrect |
22 ms |
30848 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
