Submission #679814

#	Time	Username	Problem	Language	Result	Execution time	Memory
679814		peijar	Global Warming (CEOI18_glo)	C++17	100 / 100	126 ms	13216 KiB

glo

#include <bits/stdc++.h>
#define int long long
using namespace std;

namespace std {
template <typename T> ostream &operator<<(ostream &out, const vector<T> &vec) {
  out << "[";
  for (int i = 0; i < (int)vec.size(); ++i) {
    out << vec[i];
    if (i + 1 < (int)vec.size())
      out << ", ";
  }
  return out << "]";
}
} // namespace std

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << H;
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

vector<int> calcLIS(vector<int> vec) {
  vector<int> curLis;
  int n = vec.size();
  vector<int> ret(n);
  for (int i = 0; i < n; ++i) {
    int pos =
        lower_bound(curLis.begin(), curLis.end(), vec[i]) - curLis.begin();
    ret[i] = pos + 1;
    if (pos == (int)curLis.size())
      curLis.push_back(vec[i]);
    else
      curLis[pos] = vec[i];
  }
  return ret;
}

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int n, x;
  cin >> n >> x;

  vector<int> vec(n);
  for (int &y : vec)
    cin >> y;

  vector<int> lisStart, lisEnd;

  lisEnd = calcLIS(vec);
  {
    vector<int> vec2 = vec;
    reverse(vec2.begin(), vec2.end());
    for (int &y : vec2)
      y *= -1;
    lisStart = calcLIS(vec2);
    reverse(lisStart.begin(), lisStart.end());
  }

  dbg(lisStart, lisEnd);

  set<pair<int, int>> curChoices;
  int sol = 0;
  for (int i = 0; i < n; ++i) {
    sol = max(sol, lisStart[i]);
    auto it = curChoices.lower_bound({vec[i] + x, 0LL});
    if (it != curChoices.begin()) {
      --it;
      sol = max(sol, it->second + lisStart[i]);
    }
    while ((it = curChoices.lower_bound({vec[i], 0LL})) != curChoices.end()) {
      if (it->second <= lisEnd[i])
        curChoices.erase(it);
      else
        break;
    }
    it = curChoices.lower_bound({vec[i], 0LL});
    if (it == curChoices.end() or it->first > vec[i])
      curChoices.emplace(vec[i], lisEnd[i]);
  }
  cout << sol << endl;
}

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