Submission #1130026

#TimeUsernameProblemLanguageResultExecution timeMemory
1130026micro7Global Warming (CEOI18_glo)C++17
58 / 100
257 ms23096 KiB
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
using namespace std;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, x;
  cin >> n >> x;
  vector<int> t(n);
  for (auto &i : t) {
    cin >> i;
  }

  vector<int> dp;
  map<int, vector<int>> m;
  for (int i = 0; i < n; ++i) {
    auto j = lower_bound(dp.begin(), dp.end(), t[i]);
    if (j == dp.end()) {
      dp.push_back(t[i]);
      m[t[i]].push_back(dp.size());
    } else {
      *j = t[i];
      m[t[i]].push_back(j - dp.begin() + 1);
    }
  }

  int ans = dp.size();
  dp.clear();
  for (int i = n - 1; i > 0; --i) {
    m[t[i]].pop_back();
    if (m[t[i]].empty()) {
      m.erase(t[i]);
    }
    auto j = lower_bound(dp.begin(), dp.end(), t[i], greater<>());
    int l2;
    if (j == dp.end()) {
      dp.push_back(t[i]);
      l2 = dp.size();
    } else {
      *j = t[i];
      l2 = j - dp.begin() + 1;
    }
    auto it = m.lower_bound(t[i] + x);
    ans = max(ans, it == m.begin() ? l2 : l2 + prev(it)->second.back());
  }
  cout << ans;

  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...