제출 #493573

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
493573		600Mihnea	Financial Report (JOI21_financial)	C++17	48 / 100	4062 ms	12360 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 300000 + 7;
int n, d, a[N], ord[N], l[N], r[N], t[N];

bool cmp(int i, int j) {
  if (a[i] != a[j]) {
    return a[i] > a[j];
  } else {
    return i < j;
  }
}

int getroot(int a) {
  if (t[a] == a) {
    return a;
  } else {
    return t[a] = getroot(t[a]);
  }
}

void unite(int a, int b) {
  a = getroot(a);
  b = getroot(b);
  if (a == b) {
    return;
  }
  t[a] = b;
  l[b] = min(l[b], l[a]);
  r[b] = max(r[b], r[b]);
}

int last[N], tree[4 * N];

void upd(int v, int tl, int tr, int i, int x) {
  if (tr < i || i < tl) {
    return;
  }
  if (tl == tr) {
    tree[v] = x;
    return;
  }
  int tm = (tl + tr) / 2;
  upd(2 * v, tl, tm, i, x);
  upd(2 * v + 1, tm + 1, tr, i, x);
  tree[v] = max(tree[2 * v], tree[2 * v + 1]);
}

int get(int v, int tl, int tr, int l, int r) {
  if (tr < l || r < tl) {
    return 0;
  }
  if (l <= tl && tr <= r) {
    return tree[v];
  }
  int tm = (tl + tr) / 2;
  return max(get(2 * v, tl, tm, l, r), get(2 * v + 1, tm + 1, tr, l, r));
}

int dp[N];

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);

  //freopen ("TonyStark", "r", stdin);

  cin >> n >> d;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    ord[i] = i;
  }
  sort(ord + 1, ord + n + 1, cmp);
  set<int> p;
  for (int it = 1; it <= n; it++) {
    int i = ord[it];
    {
      auto iter = p.lower_bound(i);
      if (iter == p.end()) {
        last[i] = n;
      } else {
        last[i] = min(*iter - 1 + d, n);
      }
      assert(i <= last[i]);
    }
    int dp = get(1, 1, n, i, last[i]) + 1;
    upd(1, 1, n, i, dp);
    l[i] = r[i] = t[i] = i;
    if (l[i - 1]) {
      unite(i, i - 1);
    }
    if (l[i + 1]) {
      unite(i, i + 1);
    }
    int len = r[getroot(i)] - l[getroot(i)] + 1;
    if (len >= d) {
      p.insert(l[getroot(i)]);
    }
  }
  for (int i = n; i >= 1; i--) {
    dp[i] = 0;
    int bigger = 0;
    for (int j = i + 1; j <= n; j++) {
      if (a[i] < a[j]) {
        dp[i] = max(dp[i], dp[j]);
        bigger++;
        if (bigger == d) {
          break;
        }
      } else {
        bigger = 0;
      }
    }
    dp[i]++;
  }

  int sol = 0;
  for (int i = 1; i <= n; i++) {
    sol = max(sol, dp[i]);
  }
  cout << sol << "\n";
  //cout << get(1, 1, n, 1, n) << "\n";

}

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