Submission #736773

#TimeUsernameProblemLanguageResultExecution timeMemory
736773veehzFinancial Report (JOI21_financial)C++17
12 / 100
232 ms32128 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; #define pb push_back /* Segment Tree */ template <class S, S (*op)(S, S), S (*e)()> struct segtree { /* S op(S a, S b) {} -> Combine values */ /* S e() {} -> Initial value (0) */ int _n; vector<S> d; segtree() : segtree(0) {} explicit segtree(int n) : segtree(vector<S>(n, e())) {} explicit segtree(vector<S> v) : _n(int(v.size())) { d.assign(4 * _n, e()); build(v); } void build(vector<S>& a, int v = 1, int tl = 0, int tr = -1) { if (tr == -1) tr = _n - 1; if (tl == tr) { d[v] = a[tl]; } else { int tm = (tl + tr) / 2; build(a, v * 2, tl, tm); build(a, v * 2 + 1, tm + 1, tr); d[v] = op(d[v * 2], d[v * 2 + 1]); } } void set(int pos, S new_val, int tl = 0, int tr = -1, int v = 1) { assert(0 <= pos && pos < _n); if (tr == -1) tr = _n - 1; if (tl == tr) { d[v] = new_val; } else { int tm = (tl + tr) / 2; if (pos <= tm) set(pos, new_val, tl, tm, v * 2); else set(pos, new_val, tm + 1, tr, v * 2 + 1); d[v] = op(d[2 * v], d[2 * v + 1]); } } S prod(int l, int r, int tl = 0, int tr = -1, int v = 1) { if (tr == -1) tr = _n - 1; if (r < l) return e(); if (l == tl && r == tr) return d[v]; int tm = (tl + tr) / 2; return op(prod(l, min(r, tm), tl, tm, 2 * v), prod(max(l, tm + 1), r, tm + 1, tr, 2 * v + 1)); } // new - might have bugs size_t prod_lower_bound(S x, int tl = 0, int tr = -1, int v = 1, S acc = e()) { if (tr == -1) { if (prod(0, _n - 1) < x) return _n; tr = _n - 1; } if (tl == tr) return tl; int tm = (tl + tr) / 2; if (op(acc, d[2 * v]) < x) return prod_lower_bound(x, tm + 1, tr, 2 * v + 1, op(acc, d[2 * v])); else return prod_lower_bound(x, tl, tm, 2 * v, acc); } size_t prod_upper_bound(S x, int tl = 0, int tr = -1, int v = 1, S acc = e()) { if (tr == -1) { if (prod(0, _n - 1) <= x) return _n; tr = _n - 1; } if (tl == tr) return tl; int tm = (tl + tr) / 2; if (op(acc, d[2 * v]) <= x) return prod_upper_bound(x, tm + 1, tr, 2 * v + 1, op(acc, d[2 * v])); else return prod_upper_bound(x, tl, tm, 2 * v, acc); } }; /* End: Segment Tree */ ll op(ll a, ll b) { return max(a, b); } ll e() { return 0; } int main() { int n, d; cin >> n >> d; vector<int> v(n); for (int i = 0; i < n; i++) cin >> v[i]; do { // compression vector<int> dd = v; sort(dd.begin(), dd.end()); dd.resize(unique(dd.begin(), dd.end()) - dd.begin()); for (int i = 0; i < n; i++) { v[i] = lower_bound(dd.begin(), dd.end(), v[i]) - dd.begin(); } } while (false); int mx = *max_element(v.begin(), v.end()); if (d == 1) { stack<int> s; int ans = 0; for (int i = n; i--;) { while (s.size() && s.top() <= v[i]) s.pop(); s.push(v[i]); ans = max(ans, (int)s.size()); } cout << ans << endl; return 0; } if (d == n) { segtree<ll, op, e> st(mx+1); for (int i = 0; i < n; i++) { st.set(v[i], st.prod(0, v[i]) + 1); } cout << st.prod(0, mx) << endl; } #ifdef HZLOCAL cout << mx << endl; cout << "V: "; for (auto x : v) cout << x << " "; cout << endl; #endif vector<vector<int>> dp(n, vector<int>(mx + 1, 0)); vector<multiset<int>> cmax(mx + 1); for (int i = 0; i < n; i++) { int prev, cur = 0; for (int j = 0; j <= mx; j++) { prev = cur; if (cmax[j].size()) { cur = max(cur, *cmax[j].rbegin()); } if (j < v[i]) continue; int candidate = max(cur, j ? dp[i][j - 1] : 0); if (v[i] == j) candidate = max(candidate, j ? prev + 1 : 1); dp[i][j] = candidate; } if (i >= d) { for (int j = 0; j <= mx; j++) { cmax[j].erase(cmax[j].find(dp[i - d][j])); } } for (int j = 0; j <= mx; j++) { cmax[j].insert(dp[i][j]); } } #ifdef HZLOCAL for (auto x : dp) { for (auto y : x) cout << y << " "; cout << endl; } #endif cout << *max_element(dp[n - 1].begin(), dp[n - 1].end()) << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...