Submission #736778

#	Time	Username	Problem	Language	Result	Execution time	Memory
736778		veehz	Financial Report (JOI21_financial)	C++17	45 / 100	4037 ms	187504 KiB

Main

#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], max(st.prod(v[i],v[i]), st.prod(0, v[i]-1) + 1));
    }
    cout << st.prod(0, mx) << endl;
    return 0;
  }

#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;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 0 / 20
• Subtask 4: 12 / 12
• Subtask 5: 5 / 5
• Subtask 6: 0 / 35