Submission #1295610

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295610		lmquan	Financial Report (JOI21_financial)	C++20	100 / 100	273 ms	47724 KiB

Main

#define taskname ""
#include <bits/stdc++.h>
using namespace std;
const int kMaxN = 300005;
const int kMaxLog = 20;

int n, d, a[kMaxN], c[kMaxN];
int dp[kMaxN], spt[kMaxLog][kMaxN];
vector<int> v, g[kMaxN];

struct SegmentTree {
  int n;
  vector<int> st;

  SegmentTree() {}
  SegmentTree(int _n) : n(_n) {
    st.resize(4 * n + 1, 0);
  }

  void Update(int node_id, int l, int r, int pos, int val) {
    if (l == r) {
      st[node_id] = val;
    } else {
      int mid = (l + r) / 2;

      if (pos <= mid) {
        Update(2 * node_id, l, mid, pos, val);
      } else {
        Update(2 * node_id + 1, mid + 1, r, pos, val);
      }

      st[node_id] = max(st[2 * node_id], st[2 * node_id + 1]);
    }
  }

  int Query(int node_id, int l, int r, int ql, int qr) {
    if (qr < l || ql > r) {
      return 0;
    }
    if (ql <= l && r <= qr) {
      return st[node_id];
    }

    int mid = (l + r) / 2;

    return max(Query(2 * node_id, l, mid, ql, qr), Query(2 * node_id + 1, mid + 1, r, ql, qr));
  }
} tree;

int main() {
  if (fopen(taskname".inp", "r")) {
    freopen(taskname".inp", "r", stdin);
    freopen(taskname".out", "w", stdout);
  }
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> n >> d;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    v.push_back(a[i]);
  }

  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());

  deque<int> q;

  for (int i = n; i >= 1; i--) {
    a[i] = upper_bound(v.begin(), v.end(), a[i]) - v.begin();

    while (!q.empty() && a[q.back()] >= a[i]) {
      q.pop_back();
    }

    while (!q.empty() && q.front() >= i + d) {
      q.pop_front();
    }

    q.push_back(i);

    spt[0][i] = a[q.front()];
  }

  for (int i = 1; i <= n; i++) {
    g[a[i]].push_back(i);
  }

  for (int i = 1; i < kMaxLog; i++) {
    for (int j = 1; j + (1 << i) - 1 <= n; j++) {
      spt[i][j] = max(spt[i - 1][j], spt[i - 1][j + (1 << (i - 1))]);
    }
  }

  auto Max = [&](int l, int r) -> int {
    int k = __lg(r - l + 1);
    return max(spt[k][l], spt[k][r - (1 << k) + 1]);
  };

  for (int i = 1; i <= n; i++) {
    int low = 1, high = i - d, x = 1;

    while (low <= high) {
      int mid = (low + high) / 2;

      if (Max(mid, i - d) >= a[i]) {
        x = mid, low = mid + 1;
      } else {
        high = mid - 1;
      }

    }

    c[i] = x;
  }

  tree = SegmentTree(n);

  for (int i = 1; i <= v.size(); i++) {
    for (int j : g[i]) {
      dp[j] = tree.Query(1, 1, n, c[j], j - 1) + 1;
    }

    for (int j : g[i]) {
      tree.Update(1, 1, n, j, dp[j]);
    }
  }

  cout << *max_element(dp + 1, dp + n + 1);

  return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:52:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |     freopen(taskname".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:53:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |     freopen(taskname".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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