제출 #1083450

#제출 시각아이디문제언어결과실행 시간메모리
1083450juicyGlobal Warming (CEOI18_glo)C++17
100 / 100
89 ms5636 KiB
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 2e5 + 5;

int n, x;
int a[N], ft[2][N];

int qry(int i, int *s) {
  int res = 0;
  for (; i; i -= i & -i) {
    res = max(res, s[i]);
  }
  return res;
}

void upd(int i, int x, int *s) {
  for (; i < N; i += i & -i) {
    s[i] = max(s[i], x);
  }
} 

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

  cin >> n >> x;
  vector<int> comp;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    comp.push_back(a[i]);
  }
  sort(comp.begin(), comp.end());
  comp.erase(unique(comp.begin(), comp.end()), comp.end());
  auto id = [&](int x) {
    return lower_bound(comp.begin(), comp.end(), x) - comp.begin() + 1;
  };
  int res = 0;
  for (int i = 1; i <= n; ++i) {
    array<int, 2> dp{};
    int p = id(a[i]);
    dp[0] = qry(p - 1, ft[0]) + 1;
    dp[1] = max(qry(p - 1, ft[1]), qry(id(a[i] + x) - 1, ft[0])) + 1;
    upd(p, dp[0], ft[0]);
    upd(p, dp[1], ft[1]);
    res = max(res, dp[1]);
  } 
  cout << res;
  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...