Submission #998926

#TimeUsernameProblemLanguageResultExecution timeMemory
998926abczzConstellation 3 (JOI20_constellation3)C++17
0 / 100
5 ms29532 KiB
#include <iostream> #include <array> #include <vector> #define ll long long using namespace std; vector <array<ll, 2>> V[200002]; vector <ll> H[200002]; vector <ll> U; array<ll, 2> R[200002][2]; vector <ll> adj[200002][2]; ll n, m, l, r, mid, f, s, z, mx, opt, cnt, A[200002], bl[200002][19], br[200002][19], x, y, c; struct SegTree_MAX{ ll st[800008]; void update(ll id, ll l, ll r, ll q, ll w) { if (l == r) { st[id] = max(st[id], w); return; } ll mid = (l+r)/2; if (q <= mid) update(id*2, l, mid, q, w); else update(id*2+1, mid+1, r, q, w); st[id] = max(st[id*2], st[id*2+1]); } ll query(ll id, ll l, ll r, ll ql, ll qr) { if (qr < l || r < ql) return 0; else if (ql <= l && r <= qr) return st[id]; ll mid = (l+r)/2; return max(query(id*2, l, mid, ql, qr), query(id*2+1, mid+1, r, ql, qr)); } }ST; struct SegTree_ADD{ ll st[800008], lazy[800008]; void push(ll id) { st[id*2] += lazy[id]; lazy[id*2] += lazy[id]; st[id*2+1] += lazy[id]; lazy[id*2+1] += lazy[id]; lazy[id] = 0; } void update(ll id, ll l, ll r, ll ql, ll qr, ll w) { if (qr < l || r < ql) return; else if (ql <= l && r <= qr) { st[id] += w; lazy[id] += w; return; } push(id); ll mid = (l+r)/2; update(id*2, l, mid, ql, qr, w); update(id*2+1, mid+1, r, ql, qr, w); } ll query(ll id, ll l, ll r, ll q) { if (l == r) return st[id]; push(id); ll mid = (l+r)/2; if (q <= mid) return query(id*2, l, mid, q); else return query(id*2+1, mid+1, r, q); } }tree[2]; void dfs(ll id, ll u) { R[u][id][0] = cnt; for (auto v : adj[u][id]) { dfs(id, v); } R[u][id][1] = cnt++; } int main() { cin >> n; A[0] = 1e18; for (int i=1; i<=n; ++i) { cin >> A[i]; if (A[i] > mx) { mx = A[i]; z = i; } --A[i]; } A[n+1] = 1e18; cin >> m; for (int i=0; i<m; ++i) { cin >> x >> y >> c; --y; f += c; V[y].push_back({x, c}); } V[n].push_back({z, 0}); for (int i=0; i<=n+1; ++i) { while (!U.empty() && A[U.back()] < A[i]) U.pop_back(); if (U.empty()) bl[i][0] = i; else bl[i][0] = U.back(); U.push_back(i); if (i != bl[i][0]) adj[bl[i][0]][0].push_back(i); } U.clear(); for (int i=n+1; i>=0; --i) { while (!U.empty() && A[U.back()] < A[i]) U.pop_back(); if (U.empty()) br[i][0] = i; else br[i][0] = U.back(); U.push_back(i); if (i != br[i][0]) adj[br[i][0]][1].push_back(i); } dfs(0, 0); cnt = 0; dfs(1, n+1); for (int i=1; i<=n; ++i) { H[A[i]].push_back(i); } for (int i=0; i<=n; ++i) { for (auto [x, w] : V[i]) { s = tree[0].query(1, 0, n+1, R[x][0][1]) + tree[1].query(1, 0, n+1, R[x][1][1]) + w; //cout << "? " << R[x][1][1] << " " << tree[1].query(1, 0, n+1, R[x][1][1]) << endl; //cout << x << " " << i+1 << " " << s << endl; opt = max(opt, s); ST.update(1, 0, n+1, x, s); } for (auto u : H[i]) { s = ST.query(1, 0, n+1, bl[u][0], u); //cout << i << " " << bl[u][0] << " " << u << " " << s << endl; tree[0].update(1, 0, n+1, R[u][0][0], R[u][0][1], s); z = ST.query(1, 0, n+1, u, br[u][0]); //cout << u << " " << R[u][1][0] << " " << R[u][1][1] << " " << z << endl; //cout << i << " " << u << " " << br[u][0] << " " << z << endl; tree[1].update(1, 0, n+1, R[u][1][0], R[u][1][1], z); //cout << u << " " << s << " " << z << endl; //opt = max(opt, s+z); } } cout << f-opt << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...