Submission #654128

#	Time	Username	Problem	Language	Result	Execution time	Memory
654128		Behradm	Financial Report (JOI21_financial)	C++17	0 / 100	264 ms	8020 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define lc id << 1
#define rc id << 1 | 1
#define sz(x) (int) ((x).size())

const int N = 3e5 + 5, inf = 2e9;
int a[N], dp[N][2], seg[2][N << 2];
int n;

void Modify(int j, int i, int x, int s = 1, int e = n, int id = 1) {
  if (s == e) {
    seg[j][id] = x;
    return;
  }
  int m = (s + e) >> 1;
  if (i <= m)
    Modify(j, i, x, s, m, lc);
  else
    Modify(j, i, x, m + 1, e, rc);
  seg[j][id] = max(seg[j][lc], seg[j][rc]);
}

int Get(int j, int l, int r, int s = 1, int e = n, int id = 1) {
  if (r < s || e < l)
    return 0;
  if (l <= s && e <= r)
    return seg[j][id];
  int m = (s + e) >> 1;
  return max(Get(j, l, r, s, m, lc), Get(j, l, r, m + 1, e, rc));
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int d;
  cin >> n >> d;
  for (int i = 1; i <= n; i++)
    cin >> a[i];

  a[0] = -inf;
  dp[0][0] = dp[0][1] = 1;
  vector<int> st;
  st.push_back(0);
  set<int> bad;
  for (int i = 1; i <= n; i++) {
    while (!st.empty() && a[st.back()] >= a[i]) {
      int j = st.back();
      if (bad.count(j))
        bad.erase(j);
      Modify(0, sz(st), 0);
      st.pop_back();
    }
    if (i - st.back() > d)
      bad.insert(sz(st) + 1);
    st.push_back(i);

    int k = sz(st);
    if (bad.empty()) {
      dp[i][1] = max(dp[i][1], Get(0, 1, k) + 1);
    } else {
      int j = *bad.rbegin();
      dp[i][1] = max(dp[i][1], Get(0, j, k) + 1);
    }
    Modify(0, k, dp[i][1]);


    dp[i][0] = max(dp[i][1], Get(1, max(1, i - d), i));
    Modify(1, i, dp[i][0]);
  }
  cout << dp[n][0] << '\n';
  return 0;
}

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