Submission #1130026

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130026		micro7	Global Warming (CEOI18_glo)	C++17	58 / 100	257 ms	23096 KiB

glo

#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;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25