Submission #213309

#TimeUsernameProblemLanguageResultExecution timeMemory
213309keko37Constellation 3 (JOI20_constellation3)C++14
0 / 100
8 ms5120 KiB
#include<bits/stdc++.h> using namespace std; typedef long long llint; typedef pair <int, int> pi; const int MAXN = 200005; llint n, m, ofs = 1, sum; llint 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...