Submission #1014702

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014702		kilkuwu	Financial Report (JOI21_financial)	C++17	5 / 100	302 ms	212364 KiB

Main

#include <bits/stdc++.h>

#define nl '\n'

#ifdef LOCAL
#include "template/debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif


template <typename T, typename F = std::plus<T>>
struct IterativeSegmentTree {
  int n;
  std::vector<T> tree;

  IterativeSegmentTree() {}
  IterativeSegmentTree(int _n) { init(_n); }

  void init(int _n) {
    n = _n;
    tree.assign(2 * n, T());
  }

  template <typename Vec>
  void build(const Vec& v) {
    init(v.size());
    for (int i = n; i < 2 * n; i++) tree[i] = T::from_value(v[i - n]);
    for (int i = n - 1; i > 0; i--)
      tree[i] = F()(tree[i << 1], tree[i << 1 | 1]);
  }

  template <typename Vec>
  IterativeSegmentTree(const Vec& a) {
    build(a);
  }

  void modify(int p, const T& v) {
    for (tree[p += n] = v; p >>= 1;) {
      tree[p] = F()(tree[p << 1], tree[p << 1 | 1]);
    }
  }

  T query(int l, int r) {
    T resl = T(), resr = T();
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
      if (l & 1) resl = F()(resl, tree[l++]);
      if (r & 1) resr = F()(tree[--r], resr);
    }
    return F()(resl, resr);
  }

  T get(int i) const {
    return tree[i + n];
  }
};

struct Info {
  int64_t v = -1e9;

  Info() {}
  Info(int64_t x) : v(x) {}


  static Info from_value(int64_t x) {
    return {x};
  }

  friend Info operator+(const Info& l, const Info& r) {
    return {std::max(l.v, r.v)};
  }
};

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int n, d;
  std::cin >> n >> d;

  std::vector<int> a(n);

  for (int i = 0; i < n; i++) {
    std::cin >> a[i];
  }

  int sz;
  {
    auto v = a;
    std::sort(v.begin(), v.end());
    v.erase(std::unique(v.begin(), v.end()), v.end());

    for (int i = 0; i < n; i++) {
      a[i] = std::lower_bound(v.begin(), v.end(), a[i]) - v.begin();
    }
    sz = v.size();
  }


  IterativeSegmentTree<Info> tree(sz);

  std::vector<std::deque<int>> dq(sz);

  std::vector<int> dp(n);

  auto add = [&](int x, int v) {
    while (dq[x].size() && dp[dq[x].back()] < dp[v]) {
      dq[x].pop_back();
    }
    dq[x].push_back(v);
    tree.modify(x, dp[dq[x].front()]);
  };

  auto rem = [&](int x, int v) { 
    while (dq[x].size() && dq[x].front() <= v) {
      dq[x].pop_front();
    }
    tree.modify(x, dq[x].size() ? dp[dq[x].front()] : -1e9);
  };


  for (int i = 0; i < n; i++) {
    dp[i] = 1;
    int cand = tree.query(0, a[i]).v + 1;
    dp[i] = std::max(dp[i], cand);
    add(a[i], i);
    if (i - d >= 0) {
      rem(a[i - d], i - d);
    }
  }

  std::cout << *std::max_element(dp.begin(), dp.end()) << nl;
}

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