Submission #212475

#TimeUsernameProblemLanguageResultExecution timeMemory
212475BTheroConstellation 3 (JOI20_constellation3)C++17
35 / 100
1589 ms51672 KiB
#define DBG 1 // chrono::system_clock::now().time_since_epoch().count() #include<bits/stdc++.h> //#include<ext/pb_ds/tree_policy.hpp> //#include<ext/pb_ds/assoc_container.hpp> #define pb push_back #define eb emplace_back #define mp make_pair #define fi first #define se second #define all(x) (x).begin(), (x).end() #define debug(x) if (DBG) cerr << #x << " = " << x << endl; using namespace std; //using namespace __gnu_pbds; typedef long long ll; typedef pair<int, int> pii; //template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; const int MAXN = (int)2e5 + 5; pii t[MAXN << 2]; vector<pii> S[MAXN]; ll dp[MAXN]; vector<int> adj[MAXN]; pii seg[MAXN]; int n, m, sz; int arr[MAXN]; void build(int v, int tl, int tr) { if (tl == tr) { t[v] = mp(arr[tl], tl); return; } int mid = (tl + tr) >> 1; int c1 = (v << 1), c2 = (c1 | 1); build(c1, tl, mid); build(c2, mid + 1, tr); t[v] = max(t[c1], t[c2]); } pii segMax(int v, int tl, int tr, int l, int r) { if (l > r || tl > r || tr < l) { return mp(-1, 0); } if (l <= tl && tr <= r) { return t[v]; } int mid = (tl + tr) >> 1; int c1 = (v << 1), c2 = (c1 | 1); return max(segMax(c1, tl, mid, l, r), segMax(c2, mid + 1, tr, l, r)); } void del(int v, int tl, int tr, int p) { if (tl == tr) { t[v] = mp(-1, tl); return; } int mid = (tl + tr) >> 1; int c1 = (v << 1), c2 = (c1 | 1); if (p <= mid) { del(c1, tl, mid, p); } else { del(c2, mid + 1, tr, p); } t[v] = max(t[c1], t[c2]); } ll go(int v, int x) { if (seg[v].fi > x || seg[v].se < x) { return dp[v]; } ll ret = 0; for (int to : adj[v]) { ret += go(to, x); } return ret; } int calc(int l, int r, int h = n) { int v = ++sz; seg[v] = mp(l, r); pii tmp = segMax(1, 1, n, l, r); int mx = tmp.fi; vector<int> hi; hi.pb(tmp.se); hi.pb(l - 1); hi.pb(r + 1); del(1, 1, n, tmp.se); while (1) { tmp = segMax(1, 1, n, l, r); if (tmp.fi < mx) { break; } hi.pb(tmp.se); del(1, 1, n, tmp.se); } sort(all(hi)); ll best = 0; for (int i = 0; i + 1 < hi.size(); ++i) { if (i > 0) { int x = hi[i]; auto it = lower_bound(all(S[x]), mp(mx + 1, 0)); while (it != S[x].end() && it -> fi <= h) { best = max(best, (ll)it -> se); ++it; } } int cl = hi[i] + 1; int cr = hi[i + 1] - 1; if (cl <= cr) { int to = calc(cl, cr, mx); adj[v].pb(to); dp[v] += dp[to]; for (int x = cl; x <= cr; ++x) { auto it = lower_bound(all(S[x]), mp(mx + 1, 0)); while (it != S[x].end() && it -> fi <= h) { best = max(best, -dp[to] + it -> se + go(to, x)); ++it; } } } } dp[v] += best; return v; } void solve() { scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d", &arr[i]); } ll sum = 0; scanf("%d", &m); for (int i = 1; i <= m; ++i) { int x, y, c; scanf("%d %d %d", &x, &y, &c); S[x].pb(mp(y, c)); sum += c; } for (int i = 1; i <= n; ++i) { sort(all(S[i])); } build(1, 1, n); printf("%lld\n", sum - dp[calc(1, n)]); } int main() { int tt = 1; while (tt--) { solve(); } return 0; }

Compilation message (stderr)

constellation3.cpp: In function 'int calc(int, int, int)':
constellation3.cpp:121:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i + 1 < hi.size(); ++i) {
                     ~~~~~~^~~~~~~~~~~
constellation3.cpp: In function 'void solve()':
constellation3.cpp:156:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
constellation3.cpp:159:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &arr[i]);
         ~~~~~^~~~~~~~~~~~~~~
constellation3.cpp:163:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &m);
     ~~~~~^~~~~~~~~~
constellation3.cpp:167:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &x, &y, &c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...